home *** CD-ROM | disk | FTP | other *** search
| MacBinary | 1996-02-13 | 14.3 KB | [TEXT/R*ch] |
open in: 
MacOS 8.1
|
Win98
|
DOS
browse contents |
view JSON data
|
view as text
This file was processed as: MacBinary
(archive/macBinary).
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 66%
| dexvert
| Compact Compressed (Unix) (archive/compact)
| ext
| Supported |
| 10%
| dexvert
| MacBinary (archive/macBinary)
| fallback
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| MacBinary II, inited, Mon Feb 12 20:18:52 1996, modified Mon Feb 12 20:18:52 1996, creator BBEdit, type ASCII, 12852 bytes "IntersectRects.c" , at 0x32b4 1454 bytes resource
| default (weak)
| |
| 99%
| file
| data
| default
| |
| 74%
| TrID
| Macintosh plain text (MacBinary)
| default
| |
| 25%
| TrID
| MacBinary 2
| default (weak)
| |
| 100%
| siegfried
| fmt/1762 MacBinary (II)
| default
| |
| 100%
| lsar
| MacBinary
| default
|
|
| id metadata |
|---|
| key | value |
|---|
| macFileType | [TEXT] |
| macFileCreator | [R*ch] |
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 10 49 6e 74 65 72 73 | 65 63 74 52 65 63 74 73 |..Inters|ectRects|
|00000010| 2e 63 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |.c......|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 52 2a 63 | 68 01 00 00 00 00 00 00 |.TEXTR*c|h.......|
|00000050| 00 00 00 00 00 32 34 00 | 00 05 ae ad 45 97 7c ad |.....24.|....E.|.|
|00000060| 45 97 7c 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |E.|.....|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 dc 09 00 00 |........|........|
|00000080| 2f 2a 0d 20 20 33 31 20 | 4a 61 6e 75 61 72 79 20 |/*. 31 |January |
|00000090| 31 39 39 36 2e 0d 20 20 | 53 75 62 6d 69 73 73 69 |1996.. |Submissi|
|000000a0| 6f 6e 20 74 6f 20 4d 61 | 63 54 65 63 68 20 50 72 |on to Ma|cTech Pr|
|000000b0| 6f 67 72 61 6d 6d 65 72 | 27 73 20 63 68 61 6c 6c |ogrammer|'s chall|
|000000c0| 65 6e 67 65 20 66 6f 72 | 20 46 65 62 2d 39 36 2e |enge for| Feb-96.|
|000000d0| 0d 20 20 43 6f 70 79 72 | 69 67 68 74 20 31 39 39 |. Copyr|ight 199|
|000000e0| 36 2c 20 45 72 6e 73 74 | 20 4d 75 6e 74 65 72 2c |6, Ernst| Munter,|
|000000f0| 20 4b 61 6e 61 74 61 2c | 20 4f 4e 2c 20 43 61 6e | Kanata,| ON, Can|
|00000100| 61 64 61 2e 0d 0d 20 20 | 20 20 20 20 20 20 22 49 |ada... | "I|
|00000110| 4e 54 45 52 53 45 43 54 | 49 4e 47 20 52 45 43 54 |NTERSECT|ING RECT|
|00000120| 41 4e 47 4c 45 53 22 0d | 0d 20 20 76 65 72 73 69 |ANGLES".|. versi|
|00000130| 6f 6e 20 32 2e 30 0d 0d | 0d 20 20 54 68 65 20 50 |on 2.0..|. The P|
|00000140| 72 6f 62 6c 65 6d 0d 20 | 20 2d 2d 2d 2d 2d 2d 2d |roblem. | -------|
|00000150| 2d 2d 2d 2d 0d 20 20 47 | 69 76 65 6e 20 61 20 62 |----. G|iven a b|
|00000160| 75 6e 63 68 20 6f 66 20 | 6f 76 65 72 6c 61 70 70 |unch of |overlapp|
|00000170| 69 6e 67 20 72 65 63 74 | 61 6e 67 6c 65 73 2c 20 |ing rect|angles, |
|00000180| 63 6f 6d 70 75 74 65 20 | 61 20 73 65 74 0d 20 20 |compute |a set. |
|00000190| 6f 66 20 72 65 63 74 61 | 6e 67 6c 65 73 20 77 68 |of recta|ngles wh|
|000001a0| 69 63 68 20 63 6f 76 65 | 72 73 20 74 68 65 20 61 |ich cove|rs the a|
|000001b0| 72 65 61 20 6f 66 20 65 | 69 74 68 65 72 20 61 6e |rea of e|ither an|
|000001c0| 20 6f 64 64 20 6f 72 0d | 20 20 61 6e 20 65 76 65 | odd or.| an eve|
|000001d0| 6e 20 6e 75 6d 62 65 72 | 20 6f 66 20 6f 76 65 72 |n number| of over|
|000001e0| 6c 61 70 73 2e 20 20 54 | 68 65 20 6f 75 74 70 75 |laps. T|he outpu|
|000001f0| 74 20 72 65 63 74 73 20 | 73 68 6f 75 6c 64 20 6f |t rects |should o|
|00000200| 6e 6c 79 0d 20 20 75 73 | 65 20 65 64 67 65 73 20 |nly. us|e edges |
|00000210| 66 72 6f 6d 20 74 68 65 | 20 72 65 70 65 72 74 6f |from the| reperto|
|00000220| 69 72 65 20 6f 66 20 65 | 64 67 65 73 20 63 6f 6e |ire of e|dges con|
|00000230| 74 61 69 6e 65 64 20 69 | 6e 20 74 68 65 0d 20 20 |tained i|n the. |
|00000240| 69 6e 70 75 74 20 73 65 | 74 20 6f 66 20 72 65 63 |input se|t of rec|
|00000250| 74 73 2e 0d 0d 20 20 47 | 65 6e 65 72 61 6c 20 53 |ts... G|eneral S|
|00000260| 74 72 61 74 65 67 79 0d | 20 20 2d 2d 2d 2d 2d 2d |trategy.| ------|
|00000270| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 0d 20 20 57 65 20 |--------|--. We |
|00000280| 63 72 65 61 74 65 20 61 | 20 76 69 72 74 75 61 6c |create a| virtual|
|00000290| 20 72 61 73 74 65 72 20 | 77 69 74 68 20 61 20 28 | raster |with a (|
|000002a0| 76 61 72 69 61 62 6c 65 | 29 20 72 65 73 6f 6c 75 |variable|) resolu|
|000002b0| 74 69 6f 6e 2c 0d 20 20 | 77 68 65 72 65 20 65 61 |tion,. |where ea|
|000002c0| 63 68 20 78 20 6f 72 20 | 79 20 63 6f 6f 72 64 69 |ch x or |y coordi|
|000002d0| 6e 61 74 65 20 76 61 6c | 75 65 20 63 6f 72 72 65 |nate val|ue corre|
|000002e0| 73 70 6f 6e 64 73 20 74 | 6f 20 61 6e 0d 20 20 65 |sponds t|o an. e|
|000002f0| 64 67 65 20 6f 66 20 61 | 74 20 6c 65 61 73 74 20 |dge of a|t least |
|00000300| 6f 6e 65 20 69 6e 70 75 | 74 20 72 65 63 74 61 6e |one inpu|t rectan|
|00000310| 67 6c 65 2e 20 20 44 65 | 70 65 6e 64 69 6e 67 20 |gle. De|pending |
|00000320| 6f 6e 20 74 68 65 0d 20 | 20 6e 75 6d 62 65 72 20 |on the. | number |
|00000330| 6f 66 20 69 6e 70 75 74 | 20 72 65 63 74 73 2c 20 |of input| rects, |
|00000340| 61 6e 64 20 74 68 65 69 | 72 20 63 6f 69 6e 63 69 |and thei|r coinci|
|00000350| 64 65 6e 63 65 20 6f 66 | 20 65 64 67 65 73 2c 0d |dence of| edges,.|
|00000360| 20 20 74 68 69 73 20 72 | 61 73 74 65 72 20 6d 61 | this r|aster ma|
|00000370| 79 20 62 65 20 76 65 72 | 79 20 73 6d 61 6c 6c 2c |y be ver|y small,|
|00000380| 20 6f 72 20 66 61 69 72 | 6c 79 20 6c 61 72 67 65 | or fair|ly large|
|00000390| 2c 20 62 75 74 20 6e 65 | 76 65 72 0d 20 20 6c 61 |, but ne|ver. la|
|000003a0| 72 67 65 72 20 74 68 61 | 6e 20 74 68 65 20 73 63 |rger tha|n the sc|
|000003b0| 72 65 65 6e 20 69 74 20 | 72 65 70 72 65 73 65 6e |reen it |represen|
|000003c0| 74 73 2e 0d 0d 20 20 57 | 65 20 74 68 65 6e 20 70 |ts... W|e then p|
|000003d0| 61 69 6e 74 20 72 65 63 | 74 61 6e 67 6c 65 73 20 |aint rec|tangles |
|000003e0| 69 6e 74 6f 20 74 68 65 | 20 72 61 73 74 65 72 2c |into the| raster,|
|000003f0| 20 65 61 63 68 20 72 61 | 73 74 65 72 0d 20 20 70 | each ra|ster. p|
|00000400| 6f 69 6e 74 20 62 65 69 | 6e 67 20 72 65 70 72 65 |oint bei|ng repre|
|00000410| 73 65 6e 74 65 64 20 62 | 79 20 31 20 62 69 74 2c |sented b|y 1 bit,|
|00000420| 20 72 65 67 61 72 64 6c | 65 73 73 20 68 6f 77 20 | regardl|ess how |
|00000430| 6d 61 6e 79 0d 20 20 70 | 69 78 65 6c 73 20 61 72 |many. p|ixels ar|
|00000440| 65 20 77 69 74 68 69 6e | 20 74 68 65 20 63 6f 72 |e within| the cor|
|00000450| 72 65 73 70 6f 6e 64 69 | 6e 67 20 65 64 67 65 73 |respondi|ng edges|
|00000460| 20 6f 6e 20 74 68 65 20 | 72 65 61 6c 0d 20 20 73 | on the |real. s|
|00000470| 63 72 65 65 6e 2e 20 20 | 49 20 63 61 6c 6c 20 74 |creen. |I call t|
|00000480| 68 65 73 65 20 62 69 74 | 73 20 22 76 69 72 74 75 |hese bit|s "virtu|
|00000490| 61 6c 20 70 69 78 65 6c | 73 22 20 6f 72 20 22 76 |al pixel|s" or "v|
|000004a0| 69 78 65 6c 73 22 2e 0d | 0d 20 20 41 66 74 65 72 |ixels"..|. After|
|000004b0| 20 61 6c 6c 20 76 69 78 | 65 6c 73 20 61 72 65 20 | all vix|els are |
|000004c0| 70 61 69 6e 74 65 64 2c | 20 74 68 65 20 62 69 74 |painted,| the bit|
|000004d0| 20 6d 61 70 20 69 73 20 | 73 63 61 6e 6e 65 64 0d | map is |scanned.|
|000004e0| 20 20 74 6f 20 69 64 65 | 6e 74 69 66 79 20 72 65 | to ide|ntify re|
|000004f0| 63 74 61 6e 67 75 6c 61 | 72 20 61 72 65 61 73 20 |ctangula|r areas |
|00000500| 6f 66 20 73 65 74 20 62 | 69 74 73 2e 0d 0d 20 20 |of set b|its... |
|00000510| 54 68 65 20 76 65 72 74 | 69 63 61 6c 20 65 78 74 |The vert|ical ext|
|00000520| 65 6e 74 20 6f 66 20 65 | 61 63 68 20 6f 75 74 70 |ent of e|ach outp|
|00000530| 75 74 20 72 65 63 74 20 | 69 73 20 61 74 20 6c 65 |ut rect |is at le|
|00000540| 61 73 74 20 65 71 75 61 | 6c 0d 20 20 74 6f 20 74 |ast equa|l. to t|
|00000550| 68 65 20 64 69 73 74 61 | 6e 63 65 20 62 65 74 77 |he dista|nce betw|
|00000560| 65 65 6e 20 74 68 65 20 | 74 77 6f 20 6e 65 69 67 |een the |two neig|
|00000570| 68 62 6f 72 69 6e 67 20 | 69 6e 70 75 74 20 65 64 |hboring |input ed|
|00000580| 67 65 73 2e 0d 0d 20 20 | 57 65 20 74 68 65 6e 20 |ges... |We then |
|00000590| 66 6f 6c 6c 6f 77 20 74 | 68 65 20 73 6c 69 63 65 |follow t|he slice|
|000005a0| 20 64 6f 77 6e 20 6f 76 | 65 72 20 61 73 20 6d 61 | down ov|er as ma|
|000005b0| 6e 79 20 73 6c 69 63 65 | 73 20 61 73 0d 20 20 70 |ny slice|s as. p|
|000005c0| 6f 73 73 69 62 6c 65 20 | 74 6f 20 6d 61 78 69 6d |ossible |to maxim|
|000005d0| 69 7a 65 20 74 68 65 20 | 68 65 69 67 68 74 20 6f |ize the |height o|
|000005e0| 66 20 74 68 65 20 72 65 | 63 74 61 6e 67 6c 65 2e |f the re|ctangle.|
|000005f0| 0d 0d 20 20 4d 65 6d 6f | 72 79 20 55 73 65 0d 20 |.. Memo|ry Use. |
|00000600| 20 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 0d 20 20 54 68 | -------|---. Th|
|00000610| 65 20 6d 61 78 69 6d 75 | 6d 20 61 6d 6f 75 6e 74 |e maximu|m amount|
|00000620| 20 6f 66 20 6d 65 6d 6f | 72 79 20 61 6c 6c 6f 63 | of memo|ry alloc|
|00000630| 61 74 65 64 20 64 79 6e | 61 6d 69 63 61 6c 6c 79 |ated dyn|amically|
|00000640| 20 69 73 0d 20 20 64 65 | 74 65 72 6d 69 6e 65 64 | is. de|termined|
|00000650| 20 62 79 20 74 68 65 20 | 6e 75 6d 62 65 72 20 6f | by the |number o|
|00000660| 66 20 69 6e 70 75 74 20 | 72 65 63 74 73 2e 20 20 |f input |rects. |
|00000670| 54 68 65 20 61 63 74 75 | 61 6c 0d 20 20 61 6d 6f |The actu|al. amo|
|00000680| 75 6e 74 20 77 69 6c 6c | 20 62 65 20 6c 65 73 73 |unt will| be less|
|00000690| 20 69 66 20 73 6f 6d 65 | 20 69 6e 70 75 74 20 72 | if some| input r|
|000006a0| 65 63 74 73 20 73 68 61 | 72 65 20 65 64 67 65 0d |ects sha|re edge.|
|000006b0| 20 20 63 6f 6f 72 64 69 | 6e 61 74 65 20 76 61 6c | coordi|nate val|
|000006c0| 75 65 73 2e 0d 0d 20 20 | 41 70 70 72 6f 78 69 6d |ues... |Approxim|
|000006d0| 61 74 65 20 73 69 7a 65 | 20 6f 66 20 74 68 65 20 |ate size| of the |
|000006e0| 69 6e 64 65 78 20 68 65 | 61 70 3a 0d 20 20 28 31 |index he|ap:. (1|
|000006f0| 36 20 2a 20 6e 75 6d 52 | 65 63 74 73 49 6e 29 20 |6 * numR|ectsIn) |
|00000700| 20 62 79 74 65 73 0d 20 | 20 20 20 20 70 6c 75 73 | bytes. | plus|
|00000710| 20 61 20 66 65 77 20 6f | 76 65 72 68 65 61 64 20 | a few o|verhead |
|00000720| 62 79 74 65 73 0d 0d 20 | 20 41 70 70 72 6f 78 69 |bytes.. | Approxi|
|00000730| 6d 61 74 65 20 63 6f 6d | 62 69 6e 65 64 20 73 69 |mate com|bined si|
|00000740| 7a 65 20 6f 66 20 74 68 | 65 20 74 77 6f 20 76 69 |ze of th|e two vi|
|00000750| 78 65 6c 20 6d 61 70 73 | 3a 0d 20 20 28 6e 75 6d |xel maps|:. (num|
|00000760| 52 65 63 74 73 49 6e 20 | 2a 20 6e 75 6d 52 65 63 |RectsIn |* numRec|
|00000770| 74 73 49 6e 29 20 62 79 | 74 65 73 0d 20 20 20 20 |tsIn) by|tes. |
|00000780| 20 70 6c 75 73 20 61 20 | 66 65 77 20 6f 76 65 72 | plus a |few over|
|00000790| 68 65 61 64 20 62 79 74 | 65 73 2c 0d 20 20 20 20 |head byt|es,. |
|000007a0| 20 6d 69 6e 75 73 20 67 | 61 69 6e 20 66 72 6f 6d | minus g|ain from|
|000007b0| 20 65 6c 69 6d 69 6e 61 | 74 69 6f 6e 20 6f 66 20 | elimina|tion of |
|000007c0| 64 75 70 6c 69 63 61 74 | 65 20 76 61 6c 75 65 73 |duplicat|e values|
|000007d0| 0d 0d 20 20 41 20 64 6f | 75 62 6c 65 20 73 69 7a |.. A do|uble siz|
|000007e0| 65 20 76 69 78 65 6c 20 | 6d 61 70 20 69 73 20 61 |e vixel |map is a|
|000007f0| 6c 77 61 79 73 20 61 6c | 6c 6f 63 61 74 65 64 20 |lways al|located |
|00000800| 61 6c 74 68 6f 75 67 68 | 0d 20 20 6f 6e 6c 79 20 |although|. only |
|00000810| 74 68 65 20 65 76 65 6e | 20 70 61 72 69 74 79 20 |the even| parity |
|00000820| 63 61 73 65 20 6e 65 65 | 64 73 20 62 6f 74 68 2e |case nee|ds both.|
|00000830| 0d 0d 20 20 46 6f 72 20 | 65 78 61 6d 70 6c 65 2c |.. For |example,|
|00000840| 20 74 6f 74 61 6c 20 64 | 79 6e 61 6d 69 63 20 6d | total d|ynamic m|
|00000850| 65 6d 6f 72 79 20 66 6f | 72 20 31 30 30 20 72 65 |emory fo|r 100 re|
|00000860| 63 74 61 6e 67 6c 65 73 | 20 77 69 6c 6c 0d 20 20 |ctangles| will. |
|00000870| 62 65 20 61 62 6f 75 74 | 20 31 36 4b 2e 20 20 31 |be about| 16K. 1|
|00000880| 30 30 30 20 72 65 63 74 | 61 6e 67 6c 65 73 20 6d |000 rect|angles m|
|00000890| 69 67 68 74 20 6e 65 65 | 64 20 31 4d 42 2c 20 62 |ight nee|d 1MB, b|
|000008a0| 75 74 20 6f 6e 0d 20 20 | 61 6e 79 20 72 65 61 73 |ut on. |any reas|
|000008b0| 6f 6e 61 62 6c 65 20 73 | 69 7a 65 20 73 63 72 65 |onable s|ize scre|
|000008c0| 65 6e 2c 20 31 30 30 30 | 20 72 65 63 74 61 6e 67 |en, 1000| rectang|
|000008d0| 6c 65 73 20 77 69 6c 6c | 20 73 68 61 72 65 0d 20 |les will| share. |
|000008e0| 20 61 20 76 65 72 79 20 | 6c 61 72 67 65 20 6e 75 | a very |large nu|
|000008f0| 6d 62 65 72 20 6f 66 20 | 65 64 67 65 73 2c 20 61 |mber of |edges, a|
|00000900| 6e 64 20 77 69 6c 6c 20 | 68 61 76 65 20 63 6f 6e |nd will |have con|
|00000910| 73 69 64 65 72 61 62 6c | 79 0d 20 20 6c 65 73 73 |siderabl|y. less|
|00000920| 20 6d 65 6d 6f 72 79 20 | 61 6c 6c 6f 63 61 74 65 | memory |allocate|
|00000930| 64 2e 0d 0d 0d 20 20 4f | 74 68 65 72 20 61 73 73 |d.... O|ther ass|
|00000940| 75 6d 70 74 69 6f 6e 73 | 20 28 74 68 65 73 65 20 |umptions| (these |
|00000950| 61 72 65 20 6e 6f 74 20 | 63 68 65 63 6b 65 64 29 |are not |checked)|
|00000960| 0d 20 20 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |. -----|--------|
|00000970| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 2d 2d 2d 2d |--------|--------|
|00000980| 2d 2d 2d 2d 2d 2d 2d 2d | 2d 2d 2d 2d 0d 20 20 54 |--------|----. T|
|00000990| 68 65 72 65 20 69 73 20 | 61 74 20 6c 65 61 73 74 |here is |at least|
|000009a0| 20 6f 6e 65 20 69 6e 70 | 75 74 20 72 65 63 74 2e | one inp|ut rect.|
|000009b0| 0d 0d 20 20 41 6c 6c 20 | 69 6e 70 75 74 20 72 65 |.. All |input re|
|000009c0| 63 74 73 20 61 72 65 20 | 6c 65 67 61 6c 20 61 6e |cts are |legal an|
|000009d0| 64 20 6e 6f 74 20 65 6d | 70 74 79 2c 20 74 68 61 |d not em|pty, tha|
|000009e0| 74 20 69 73 3a 0d 20 20 | 20 20 20 20 74 6f 70 3c |t is:. | top<|
|000009f0| 62 6f 74 74 6f 6d 2c 20 | 61 6e 64 20 6c 65 66 74 |bottom, |and left|
|00000a00| 3c 72 69 67 68 74 2e 0d | 2a 2f 0d 0d 2f 2f 20 70 |<right..|*/..// p|
|00000a10| 6c 65 61 73 65 20 69 6e | 63 6c 75 64 65 20 66 72 |lease in|clude fr|
|00000a20| 6f 6d 20 74 68 65 20 66 | 6f 6c 6c 6f 77 69 6e 67 |om the f|ollowing|
|00000a30| 20 77 68 61 74 20 6d 61 | 79 20 62 65 20 6e 65 65 | what ma|y be nee|
|00000a40| 64 65 64 0d 23 69 6e 63 | 6c 75 64 65 20 3c 73 74 |ded.#inc|lude <st|
|00000a50| 64 6c 69 62 2e 68 3e 0d | 23 69 6e 63 6c 75 64 65 |dlib.h>.|#include|
|00000a60| 20 3c 73 74 64 69 6f 2e | 68 3e 0d 23 69 6e 63 6c | <stdio.|h>.#incl|
|00000a70| 75 64 65 20 3c 73 74 72 | 69 6e 67 2e 68 3e 0d 23 |ude <str|ing.h>.#|
|00000a80| 64 65 66 69 6e 65 20 4d | 41 58 4c 4f 4e 47 20 30 |define M|AXLONG 0|
|00000a90| 78 37 66 66 66 66 66 66 | 66 0d 0d 76 6f 69 64 20 |x7ffffff|f..void |
|00000aa0| 52 65 63 74 61 6e 67 6c | 65 49 6e 74 65 72 73 65 |Rectangl|eInterse|
|00000ab0| 63 74 69 6f 6e 73 28 0d | 20 20 20 20 20 63 6f 6e |ctions(.| con|
|00000ac0| 73 74 20 52 65 63 74 20 | 69 6e 70 75 74 52 65 63 |st Rect |inputRec|
|00000ad0| 74 73 5b 5d 2c 0d 20 20 | 20 20 20 63 6f 6e 73 74 |ts[],. | const|
|00000ae0| 20 6c 6f 6e 67 20 6e 75 | 6d 52 65 63 74 73 49 6e | long nu|mRectsIn|
|00000af0| 2c 0d 20 20 20 20 20 52 | 65 63 74 20 20 6f 75 74 |,. R|ect out|
|00000b00| 70 75 74 52 65 63 74 73 | 5b 5d 2c 0d 20 20 20 20 |putRects|[],. |
|00000b10| 20 6c 6f 6e 67 20 20 2a | 6e 75 6d 52 65 63 74 73 | long *|numRects|
|00000b20| 4f 75 74 2c 0d 20 20 20 | 20 20 63 6f 6e 73 74 20 |Out,. | const |
|00000b30| 42 6f 6f 6c 65 61 6e 20 | 6f 64 64 50 61 72 69 74 |Boolean |oddParit|
|00000b40| 79 29 3b 0d 0d 2f 2f 20 | 4c 6f 63 61 6c 20 66 75 |y);..// |Local fu|
|00000b50| 6e 63 74 69 6f 6e 20 70 | 72 6f 74 6f 74 79 70 65 |nction p|rototype|
|00000b60| 73 3a 0d 76 6f 69 64 20 | 20 50 61 69 6e 74 4f 64 |s:.void | PaintOd|
|00000b70| 64 28 6c 6f 6e 67 2a 20 | 76 6d 2c 6c 6f 6e 67 20 |d(long* |vm,long |
|00000b80| 48 2c 6c 6f 6e 67 20 4c | 2c 6c 6f 6e 67 20 52 2c |H,long L|,long R,|
|00000b90| 6c 6f 6e 67 20 6d 61 70 | 57 69 64 74 68 29 3b 0d |long map|Width);.|
|00000ba0| 76 6f 69 64 20 20 50 61 | 69 6e 74 45 76 65 6e 28 |void Pa|intEven(|
|00000bb0| 6c 6f 6e 67 2a 20 76 6d | 2c 6c 6f 6e 67 20 48 2c |long* vm|,long H,|
|00000bc0| 6c 6f 6e 67 20 4c 2c 6c | 6f 6e 67 20 52 2c 6c 6f |long L,l|ong R,lo|
|00000bd0| 6e 67 20 6d 61 70 57 69 | 64 74 68 29 3b 0d 76 6f |ng mapWi|dth);.vo|
|00000be0| 69 64 20 20 50 61 63 6b | 4d 61 70 28 6c 6f 6e 67 |id Pack|Map(long|
|00000bf0| 2a 20 76 6d 2c 6c 6f 6e | 67 20 6d 61 70 53 69 7a |* vm,lon|g mapSiz|
|00000c00| 65 29 3b 0d 76 6f 69 64 | 20 20 49 6e 73 65 72 74 |e);.void| Insert|
|00000c10| 28 6c 6f 6e 67 2a 20 68 | 2c 6c 6f 6e 67 20 73 69 |(long* h|,long si|
|00000c20| 7a 65 2c 6c 6f 6e 67 20 | 78 29 3b 0d 6c 6f 6e 67 |ze,long |x);.long|
|00000c30| 2a 20 53 6f 72 74 28 6c | 6f 6e 67 2a 20 68 2c 6c |* Sort(l|ong* h,l|
|00000c40| 6f 6e 67 20 73 69 7a 65 | 29 3b 0d 6c 6f 6e 67 20 |ong size|);.long |
|00000c50| 20 47 65 74 49 6e 64 65 | 78 28 6c 6f 6e 67 20 73 | GetInde|x(long s|
|00000c60| 69 7a 65 2c 6c 6f 6e 67 | 2a 20 69 6e 64 65 78 2c |ize,long|* index,|
|00000c70| 6c 6f 6e 67 20 7a 29 3b | 0d 0d 2f 2f 53 6f 6d 65 |long z);|..//Some|
|00000c80| 20 73 68 6f 72 74 68 61 | 6e 64 20 6d 61 63 72 6f | shortha|nd macro|
|00000c90| 73 3a 0d 23 64 65 66 69 | 6e 65 20 49 52 54 20 28 |s:.#defi|ne IRT (|
|00000ca0| 69 6e 70 75 74 52 65 63 | 74 73 5b 69 5d 2e 74 6f |inputRec|ts[i].to|
|00000cb0| 70 29 0d 23 64 65 66 69 | 6e 65 20 49 52 4c 20 28 |p).#defi|ne IRL (|
|00000cc0| 69 6e 70 75 74 52 65 63 | 74 73 5b 69 5d 2e 6c 65 |inputRec|ts[i].le|
|00000cd0| 66 74 29 0d 23 64 65 66 | 69 6e 65 20 49 52 42 20 |ft).#def|ine IRB |
|00000ce0| 28 69 6e 70 75 74 52 65 | 63 74 73 5b 69 5d 2e 62 |(inputRe|cts[i].b|
|00000cf0| 6f 74 74 6f 6d 29 0d 23 | 64 65 66 69 6e 65 20 49 |ottom).#|define I|
|00000d00| 52 52 20 28 69 6e 70 75 | 74 52 65 63 74 73 5b 69 |RR (inpu|tRects[i|
|00000d10| 5d 2e 72 69 67 68 74 29 | 0d 0d 23 64 65 66 69 6e |].right)|..#defin|
|00000d20| 65 20 4f 52 54 20 28 4f | 52 70 74 72 2d 3e 74 6f |e ORT (O|Rptr->to|
|00000d30| 70 29 0d 23 64 65 66 69 | 6e 65 20 4f 52 4c 20 28 |p).#defi|ne ORL (|
|00000d40| 4f 52 70 74 72 2d 3e 6c | 65 66 74 29 0d 23 64 65 |ORptr->l|eft).#de|
|00000d50| 66 69 6e 65 20 4f 52 42 | 20 28 4f 52 70 74 72 2d |fine ORB| (ORptr-|
|00000d60| 3e 62 6f 74 74 6f 6d 29 | 0d 23 64 65 66 69 6e 65 |>bottom)|.#define|
|00000d70| 20 4f 52 52 20 28 4f 52 | 70 74 72 2d 3e 72 69 67 | ORR (OR|ptr->rig|
|00000d80| 68 74 29 0d 0d 2f 2a 20 | 4d 61 73 6b 73 20 6e 65 |ht)../* |Masks ne|
|00000d90| 65 64 65 64 20 74 6f 20 | 70 72 6f 63 65 73 73 20 |eded to |process |
|00000da0| 74 68 65 20 65 64 67 65 | 73 20 6f 66 20 76 69 78 |the edge|s of vix|
|00000db0| 65 6c 20 62 6c 6f 63 6b | 73 0d 20 20 20 77 68 69 |el block|s. whi|
|00000dc0| 63 68 20 61 72 65 20 6e | 6f 74 20 6e 65 63 65 73 |ch are n|ot neces|
|00000dd0| 73 61 72 69 6c 79 20 61 | 6c 69 67 6e 65 64 20 77 |sarily a|ligned w|
|00000de0| 69 74 68 20 62 69 74 6d | 61 70 20 77 6f 72 64 73 |ith bitm|ap words|
|00000df0| 2e 0d 2a 2f 0d 6c 6f 6e | 67 20 6c 65 66 74 4d 61 |..*/.lon|g leftMa|
|00000e00| 73 6b 5b 33 32 5d 20 3d | 0d 20 20 20 7b 30 78 46 |sk[32] =|. {0xF|
|00000e10| 46 46 46 46 46 46 46 2c | 20 30 78 37 46 46 46 46 |FFFFFFF,| 0x7FFFF|
|00000e20| 46 46 46 2c 20 30 78 33 | 46 46 46 46 46 46 46 2c |FFF, 0x3|FFFFFFF,|
|00000e30| 20 30 78 31 46 46 46 46 | 46 46 46 2c 0d 20 20 20 | 0x1FFFF|FFF,. |
|00000e40| 20 30 78 30 46 46 46 46 | 46 46 46 2c 20 30 78 30 | 0x0FFFF|FFF, 0x0|
|00000e50| 37 46 46 46 46 46 46 2c | 20 30 78 30 33 46 46 46 |7FFFFFF,| 0x03FFF|
|00000e60| 46 46 46 2c 20 30 78 30 | 31 46 46 46 46 46 46 2c |FFF, 0x0|1FFFFFF,|
|00000e70| 0d 20 20 20 20 30 78 30 | 30 46 46 46 46 46 46 2c |. 0x0|0FFFFFF,|
|00000e80| 20 30 78 30 30 37 46 46 | 46 46 46 2c 20 30 78 30 | 0x007FF|FFF, 0x0|
|00000e90| 30 33 46 46 46 46 46 2c | 20 30 78 30 30 31 46 46 |03FFFFF,| 0x001FF|
|00000ea0| 46 46 46 2c 0d 20 20 20 | 20 30 78 30 30 30 46 46 |FFF,. | 0x000FF|
|00000eb0| 46 46 46 2c 20 30 78 30 | 30 30 37 46 46 46 46 2c |FFF, 0x0|007FFFF,|
|00000ec0| 20 30 78 30 30 30 33 46 | 46 46 46 2c 20 30 78 30 | 0x0003F|FFF, 0x0|
|00000ed0| 30 30 31 46 46 46 46 2c | 0d 20 20 20 20 30 78 30 |001FFFF,|. 0x0|
|00000ee0| 30 30 30 46 46 46 46 2c | 20 30 78 30 30 30 30 37 |000FFFF,| 0x00007|
|00000ef0| 46 46 46 2c 20 30 78 30 | 30 30 30 33 46 46 46 2c |FFF, 0x0|0003FFF,|
|00000f00| 20 30 78 30 30 30 30 31 | 46 46 46 2c 0d 20 20 20 | 0x00001|FFF,. |
|00000f10| 20 30 78 30 30 30 30 30 | 46 46 46 2c 20 30 78 30 | 0x00000|FFF, 0x0|
|00000f20| 30 30 30 30 37 46 46 2c | 20 30 78 30 30 30 30 30 |00007FF,| 0x00000|
|00000f30| 33 46 46 2c 20 30 78 30 | 30 30 30 30 31 46 46 2c |3FF, 0x0|00001FF,|
|00000f40| 0d 20 20 20 20 30 78 30 | 30 30 30 30 30 46 46 2c |. 0x0|00000FF,|
|00000f50| 20 30 78 30 30 30 30 30 | 30 37 46 2c 20 30 78 30 | 0x00000|07F, 0x0|
|00000f60| 30 30 30 30 30 33 46 2c | 20 30 78 30 30 30 30 30 |000003F,| 0x00000|
|00000f70| 30 31 46 2c 0d 20 20 20 | 20 30 78 30 30 30 30 30 |01F,. | 0x00000|
|00000f80| 30 30 46 2c 20 30 78 30 | 30 30 30 30 30 30 37 2c |00F, 0x0|0000007,|
|00000f90| 20 30 78 30 30 30 30 30 | 30 30 33 2c 20 30 78 30 | 0x00000|003, 0x0|
|00000fa0| 30 30 30 30 30 30 31 7d | 3b 0d 0d 6c 6f 6e 67 20 |0000001}|;..long |
|00000fb0| 72 69 67 68 74 4d 61 73 | 6b 5b 33 32 5d 20 3d 0d |rightMas|k[32] =.|
|00000fc0| 20 20 20 7b 30 78 38 30 | 30 30 30 30 30 30 2c 20 | {0x80|000000, |
|00000fd0| 30 78 43 30 30 30 30 30 | 30 30 2c 20 30 78 45 30 |0xC00000|00, 0xE0|
|00000fe0| 30 30 30 30 30 30 2c 20 | 30 78 46 30 30 30 30 30 |000000, |0xF00000|
|00000ff0| 30 30 2c 0d 20 20 20 20 | 30 78 46 38 30 30 30 30 |00,. |0xF80000|
|00001000| 30 30 2c 20 30 78 46 43 | 30 30 30 30 30 30 2c 20 |00, 0xFC|000000, |
|00001010| 30 78 46 45 30 30 30 30 | 30 30 2c 20 30 78 46 46 |0xFE0000|00, 0xFF|
|00001020| 30 30 30 30 30 30 2c 0d | 20 20 20 20 30 78 46 46 |000000,.| 0xFF|
|00001030| 38 30 30 30 30 30 2c 20 | 30 78 46 46 43 30 30 30 |800000, |0xFFC000|
|00001040| 30 30 2c 20 30 78 46 46 | 45 30 30 30 30 30 2c 20 |00, 0xFF|E00000, |
|00001050| 30 78 46 46 46 30 30 30 | 30 30 2c 0d 20 20 20 20 |0xFFF000|00,. |
|00001060| 30 78 46 46 46 38 30 30 | 30 30 2c 20 30 78 46 46 |0xFFF800|00, 0xFF|
|00001070| 46 43 30 30 30 30 2c 20 | 30 78 46 46 46 45 30 30 |FC0000, |0xFFFE00|
|00001080| 30 30 2c 20 30 78 46 46 | 46 46 30 30 30 30 2c 0d |00, 0xFF|FF0000,.|
|00001090| 20 20 20 20 30 78 46 46 | 46 46 38 30 30 30 2c 20 | 0xFF|FF8000, |
|000010a0| 30 78 46 46 46 46 43 30 | 30 30 2c 20 30 78 46 46 |0xFFFFC0|00, 0xFF|
|000010b0| 46 46 45 30 30 30 2c 20 | 30 78 46 46 46 46 46 30 |FFE000, |0xFFFFF0|
|000010c0| 30 30 2c 0d 20 20 20 20 | 30 78 46 46 46 46 46 38 |00,. |0xFFFFF8|
|000010d0| 30 30 2c 20 30 78 46 46 | 46 46 46 43 30 30 2c 20 |00, 0xFF|FFFC00, |
|000010e0| 30 78 46 46 46 46 46 45 | 30 30 2c 20 30 78 46 46 |0xFFFFFE|00, 0xFF|
|000010f0| 46 46 46 46 30 30 2c 0d | 20 20 20 20 30 78 46 46 |FFFF00,.| 0xFF|
|00001100| 46 46 46 46 38 30 2c 20 | 30 78 46 46 46 46 46 46 |FFFF80, |0xFFFFFF|
|00001110| 43 30 2c 20 30 78 46 46 | 46 46 46 46 45 30 2c 20 |C0, 0xFF|FFFFE0, |
|00001120| 30 78 46 46 46 46 46 46 | 46 30 2c 0d 20 20 20 20 |0xFFFFFF|F0,. |
|00001130| 30 78 46 46 46 46 46 46 | 46 38 2c 20 30 78 46 46 |0xFFFFFF|F8, 0xFF|
|00001140| 46 46 46 46 46 43 2c 20 | 30 78 46 46 46 46 46 46 |FFFFFC, |0xFFFFFF|
|00001150| 46 45 2c 20 30 78 46 46 | 46 46 46 46 46 46 7d 3b |FE, 0xFF|FFFFFF};|
|00001160| 0d 0d 0d 76 6f 69 64 20 | 52 65 63 74 61 6e 67 6c |...void |Rectangl|
|00001170| 65 49 6e 74 65 72 73 65 | 63 74 69 6f 6e 73 28 0d |eInterse|ctions(.|
|00001180| 20 20 20 20 20 63 6f 6e | 73 74 20 52 65 63 74 20 | con|st Rect |
|00001190| 69 6e 70 75 74 52 65 63 | 74 73 5b 5d 2c 0d 20 20 |inputRec|ts[],. |
|000011a0| 20 20 20 63 6f 6e 73 74 | 20 6c 6f 6e 67 20 6e 75 | const| long nu|
|000011b0| 6d 52 65 63 74 73 49 6e | 2c 0d 20 20 20 20 20 52 |mRectsIn|,. R|
|000011c0| 65 63 74 20 20 6f 75 74 | 70 75 74 52 65 63 74 73 |ect out|putRects|
|000011d0| 5b 5d 2c 0d 20 20 20 20 | 20 6c 6f 6e 67 20 20 2a |[],. | long *|
|000011e0| 6e 75 6d 52 65 63 74 73 | 4f 75 74 2c 0d 20 20 20 |numRects|Out,. |
|000011f0| 20 20 63 6f 6e 73 74 20 | 42 6f 6f 6c 65 61 6e 20 | const |Boolean |
|00001200| 6f 64 64 50 61 72 69 74 | 79 29 20 7b 0d 0d 20 20 |oddParit|y) {.. |
|00001210| 20 20 6c 6f 6e 67 2a 20 | 78 48 65 61 70 3b 0d 20 | long* |xHeap;. |
|00001220| 20 20 20 6c 6f 6e 67 2a | 20 79 48 65 61 70 3b 0d | long*| yHeap;.|
|00001230| 20 20 20 20 6c 6f 6e 67 | 2a 20 76 69 78 65 6c 4d | long|* vixelM|
|00001240| 61 70 3b 0d 0d 20 20 20 | 20 6c 6f 6e 67 2a 20 78 |ap;.. | long* x|
|00001250| 49 6e 64 65 78 3b 0d 20 | 20 20 20 6c 6f 6e 67 2a |Index;. | long*|
|00001260| 20 79 49 6e 64 65 78 3b | 0d 20 20 20 20 6c 6f 6e | yIndex;|. lon|
|00001270| 67 20 20 78 49 6e 64 65 | 78 4d 61 78 3b 0d 20 20 |g xInde|xMax;. |
|00001280| 20 20 6c 6f 6e 67 20 20 | 79 49 6e 64 65 78 4d 61 | long |yIndexMa|
|00001290| 78 3b 0d 20 20 20 20 6c | 6f 6e 67 20 20 78 48 65 |x;. l|ong xHe|
|000012a0| 61 70 53 69 7a 65 3b 0d | 20 20 20 20 6c 6f 6e 67 |apSize;.| long|
|000012b0| 20 20 79 48 65 61 70 53 | 69 7a 65 3b 0d 0d 20 20 | yHeapS|ize;.. |
|000012c0| 20 20 6c 6f 6e 67 20 20 | 69 3b 0d 20 20 20 20 6c | long |i;. l|
|000012d0| 6f 6e 67 20 20 6d 61 70 | 57 69 64 74 68 3b 0d 20 |ong map|Width;. |
|000012e0| 20 20 20 6c 6f 6e 67 20 | 20 6d 61 70 53 69 7a 65 | long | mapSize|
|000012f0| 3b 0d 20 20 20 20 52 65 | 63 74 2a 20 4f 52 70 74 |;. Re|ct* ORpt|
|00001300| 72 20 3d 20 6f 75 74 70 | 75 74 52 65 63 74 73 3b |r = outp|utRects;|
|00001310| 0d 0d 2f 2f 20 20 46 69 | 72 73 74 2c 20 77 65 20 |..// Fi|rst, we |
|00001320| 63 6f 6c 6c 65 63 74 20 | 61 6c 6c 20 58 20 61 6e |collect |all X an|
|00001330| 64 20 59 20 63 6f 6f 72 | 64 69 6e 61 74 65 20 76 |d Y coor|dinate v|
|00001340| 61 6c 75 65 73 20 6f 66 | 0d 2f 2f 20 20 61 6c 6c |alues of|.// all|
|00001350| 20 69 6e 70 75 74 20 72 | 65 63 74 61 6e 67 6c 65 | input r|ectangle|
|00001360| 73 20 69 6e 20 61 20 68 | 65 61 70 20 28 70 72 69 |s in a h|eap (pri|
|00001370| 6f 72 69 74 79 20 71 75 | 65 75 65 29 2c 20 77 68 |ority qu|eue), wh|
|00001380| 69 63 68 0d 2f 2f 20 20 | 69 73 20 74 68 65 6e 20 |ich.// |is then |
|00001390| 73 6f 72 74 65 64 20 69 | 6e 74 6f 20 61 6e 20 69 |sorted i|nto an i|
|000013a0| 6e 64 65 78 20 77 69 74 | 68 6f 75 74 20 64 75 70 |ndex wit|hout dup|
|000013b0| 6c 69 63 61 74 65 73 20 | 66 6f 72 20 65 61 63 68 |licates |for each|
|000013c0| 0d 2f 2f 20 20 64 69 6d | 65 6e 73 69 6f 6e 2c 20 |.// dim|ension, |
|000013d0| 75 73 69 6e 67 20 61 20 | 6d 6f 64 69 66 69 65 64 |using a |modified|
|000013e0| 20 66 6f 72 6d 20 6f 66 | 20 48 65 61 70 73 6f 72 | form of| Heapsor|
|000013f0| 74 2e 0d 0d 20 20 20 20 | 2a 6e 75 6d 52 65 63 74 |t... |*numRect|
|00001400| 73 4f 75 74 3d 30 3b 0d | 20 20 20 20 69 66 20 28 |sOut=0;.| if (|
|00001410| 30 3d 3d 28 79 48 65 61 | 70 3d 28 6c 6f 6e 67 2a |0==(yHea|p=(long*|
|00001420| 29 6d 61 6c 6c 6f 63 28 | 28 6e 75 6d 52 65 63 74 |)malloc(|(numRect|
|00001430| 73 49 6e 2b 33 29 2a 73 | 69 7a 65 6f 66 28 6c 6f |sIn+3)*s|izeof(lo|
|00001440| 6e 67 29 2a 34 29 29 29 | 20 72 65 74 75 72 6e 3b |ng)*4)))| return;|
|00001450| 0d 20 20 20 20 78 48 65 | 61 70 3d 79 48 65 61 70 |. xHe|ap=yHeap|
|00001460| 2b 28 6e 75 6d 52 65 63 | 74 73 49 6e 2b 33 29 2a |+(numRec|tsIn+3)*|
|00001470| 32 3b 0d 0d 20 20 20 20 | 2a 78 48 65 61 70 3d 2a |2;.. |*xHeap=*|
|00001480| 79 48 65 61 70 3d 4d 41 | 58 4c 4f 4e 47 3b 0d 20 |yHeap=MA|XLONG;. |
|00001490| 20 20 20 78 48 65 61 70 | 53 69 7a 65 3d 79 48 65 | xHeap|Size=yHe|
|000014a0| 61 70 53 69 7a 65 3d 31 | 3b 0d 0d 20 20 20 20 66 |apSize=1|;.. f|
|000014b0| 6f 72 20 28 69 3d 30 3b | 69 3c 6e 75 6d 52 65 63 |or (i=0;|i<numRec|
|000014c0| 74 73 49 6e 3b 69 2b 2b | 29 20 7b 0d 20 20 20 20 |tsIn;i++|) {. |
|000014d0| 20 20 49 6e 73 65 72 74 | 28 79 48 65 61 70 2c 79 | Insert|(yHeap,y|
|000014e0| 48 65 61 70 53 69 7a 65 | 2c 49 52 54 29 3b 20 20 |HeapSize|,IRT); |
|000014f0| 20 20 79 48 65 61 70 53 | 69 7a 65 2b 2b 3b 0d 20 | yHeapS|ize++;. |
|00001500| 20 20 20 20 20 49 6e 73 | 65 72 74 28 79 48 65 61 | Ins|ert(yHea|
|00001510| 70 2c 79 48 65 61 70 53 | 69 7a 65 2c 49 52 42 29 |p,yHeapS|ize,IRB)|
|00001520| 3b 20 20 20 20 79 48 65 | 61 70 53 69 7a 65 2b 2b |; yHe|apSize++|
|00001530| 3b 0d 20 20 20 20 20 20 | 49 6e 73 65 72 74 28 78 |;. |Insert(x|
|00001540| 48 65 61 70 2c 78 48 65 | 61 70 53 69 7a 65 2c 49 |Heap,xHe|apSize,I|
|00001550| 52 4c 29 3b 20 20 20 20 | 78 48 65 61 70 53 69 7a |RL); |xHeapSiz|
|00001560| 65 2b 2b 3b 0d 20 20 20 | 20 20 20 49 6e 73 65 72 |e++;. | Inser|
|00001570| 74 28 78 48 65 61 70 2c | 78 48 65 61 70 53 69 7a |t(xHeap,|xHeapSiz|
|00001580| 65 2c 49 52 52 29 3b 20 | 20 20 20 78 48 65 61 70 |e,IRR); | xHeap|
|00001590| 53 69 7a 65 2b 2b 3b 0d | 20 20 20 20 7d 0d 0d 20 |Size++;.| }.. |
|000015a0| 20 20 20 78 49 6e 64 65 | 78 3d 53 6f 72 74 28 78 | xInde|x=Sort(x|
|000015b0| 48 65 61 70 2c 78 48 65 | 61 70 53 69 7a 65 29 3b |Heap,xHe|apSize);|
|000015c0| 0d 20 20 20 20 78 49 6e | 64 65 78 4d 61 78 3d 78 |. xIn|dexMax=x|
|000015d0| 48 65 61 70 53 69 7a 65 | 2d 28 78 49 6e 64 65 78 |HeapSize|-(xIndex|
|000015e0| 2d 78 48 65 61 70 29 3b | 0d 20 20 20 20 79 49 6e |-xHeap);|. yIn|
|000015f0| 64 65 78 3d 53 6f 72 74 | 28 79 48 65 61 70 2c 79 |dex=Sort|(yHeap,y|
|00001600| 48 65 61 70 53 69 7a 65 | 29 3b 0d 20 20 20 20 79 |HeapSize|);. y|
|00001610| 49 6e 64 65 78 4d 61 78 | 3d 79 48 65 61 70 53 69 |IndexMax|=yHeapSi|
|00001620| 7a 65 2d 28 79 49 6e 64 | 65 78 2d 79 48 65 61 70 |ze-(yInd|ex-yHeap|
|00001630| 29 3b 0d 0d 2f 2f 6e 6f | 74 65 3a 20 49 6e 64 65 |);..//no|te: Inde|
|00001640| 78 4d 61 78 20 69 6e 64 | 65 78 65 73 20 74 6f 20 |xMax ind|exes to |
|00001650| 74 68 65 20 6c 61 73 74 | 20 65 6e 74 72 79 20 69 |the last| entry i|
|00001660| 6e 64 65 78 5b 69 6e 64 | 65 78 4d 61 78 5d 0d 2f |ndex[ind|exMax]./|
|00001670| 2f 20 20 20 20 20 20 69 | 6e 20 65 61 63 68 20 69 |/ i|n each i|
|00001680| 6e 64 65 78 20 6c 69 73 | 74 2e 20 20 69 6e 64 65 |ndex lis|t. inde|
|00001690| 78 5b 30 5d 20 61 6e 64 | 20 69 6e 64 65 78 5b 69 |x[0] and| index[i|
|000016a0| 6e 64 65 78 4d 61 78 5d | 0d 2f 2f 20 20 20 20 20 |ndexMax]|.// |
|000016b0| 20 61 72 65 20 74 68 65 | 20 65 64 67 65 73 20 6f | are the| edges o|
|000016c0| 66 20 74 68 65 20 65 6e | 63 6c 6f 73 69 6e 67 20 |f the en|closing |
|000016d0| 72 65 63 74 61 6e 67 6c | 65 2e 0d 0d 0d 2f 2f 20 |rectangl|e....// |
|000016e0| 20 45 61 63 68 20 62 6c | 6f 63 6b 20 6f 66 20 72 | Each bl|ock of r|
|000016f0| 65 61 6c 20 70 69 78 65 | 6c 73 20 74 68 61 74 20 |eal pixe|ls that |
|00001700| 69 73 20 64 65 66 69 6e | 65 64 20 62 79 20 61 64 |is defin|ed by ad|
|00001710| 6a 61 63 65 6e 74 0d 2f | 2f 20 20 58 20 61 6e 64 |jacent./|/ X and|
|00001720| 20 59 20 65 64 67 65 73 | 20 28 66 72 6f 6d 20 61 | Y edges| (from a|
|00001730| 6e 79 20 69 6e 70 75 74 | 20 72 65 63 74 61 6e 67 |ny input| rectang|
|00001740| 6c 65 29 20 69 73 20 63 | 6f 6e 73 69 64 65 72 65 |le) is c|onsidere|
|00001750| 64 0d 2f 2f 20 20 61 73 | 20 61 20 73 69 6e 67 6c |d.// as| a singl|
|00001760| 65 20 76 69 72 74 75 61 | 6c 20 70 69 78 65 6c 20 |e virtua|l pixel |
|00001770| 28 22 76 69 78 65 6c 22 | 29 2e 20 20 54 68 65 20 |("vixel"|). The |
|00001780| 6d 61 70 20 6f 66 20 74 | 68 65 73 65 0d 2f 2f 20 |map of t|hese.// |
|00001790| 20 76 69 78 65 6c 73 20 | 77 69 6c 6c 20 74 68 65 | vixels |will the|
|000017a0| 6e 20 62 65 20 70 6f 70 | 75 6c 61 74 65 64 20 62 |n be pop|ulated b|
|000017b0| 79 20 74 68 65 20 69 6e | 70 75 74 20 72 65 63 74 |y the in|put rect|
|000017c0| 61 6e 67 6c 65 73 2e 0d | 2f 2f 20 20 45 61 63 68 |angles..|// Each|
|000017d0| 20 76 69 78 65 6c 20 69 | 73 20 72 65 70 72 65 73 | vixel i|s repres|
|000017e0| 65 6e 74 65 64 20 62 79 | 20 61 20 62 69 74 20 69 |ented by| a bit i|
|000017f0| 6e 20 76 69 78 65 6c 4d | 61 70 2e 0d 0d 2f 2f 20 |n vixelM|ap...// |
|00001800| 20 57 65 20 67 65 74 20 | 6d 65 6d 6f 72 79 20 66 | We get |memory f|
|00001810| 6f 72 20 74 68 65 20 76 | 69 78 65 6c 20 6d 61 70 |or the v|ixel map|
|00001820| 20 61 6e 64 20 63 6c 65 | 61 72 20 69 74 20 74 6f | and cle|ar it to|
|00001830| 20 30 2e 0d 2f 2f 20 20 | 56 69 78 65 6c 73 20 61 | 0..// |Vixels a|
|00001840| 72 65 20 73 74 6f 72 65 | 64 20 61 73 20 62 69 74 |re store|d as bit|
|00001850| 6d 61 70 73 20 69 6e 20 | 33 32 2d 62 69 74 20 77 |maps in |32-bit w|
|00001860| 6f 72 64 73 2e 0d 0d 2f | 2f 20 20 54 68 65 20 76 |ords.../|/ The v|
|00001870| 69 78 65 6c 20 6d 61 70 | 20 69 73 20 69 6e 69 74 |ixel map| is init|
|00001880| 69 61 6c 6c 79 20 6f 72 | 67 61 6e 69 7a 65 64 20 |ially or|ganized |
|00001890| 61 73 20 65 69 74 68 65 | 72 20 31 20 77 6f 72 64 |as eithe|r 1 word|
|000018a0| 0d 2f 2f 20 20 70 65 72 | 20 33 32 20 76 69 78 65 |.// per| 32 vixe|
|000018b0| 6c 73 20 28 6f 64 64 20 | 70 61 72 69 74 79 29 20 |ls (odd |parity) |
|000018c0| 6f 72 20 32 20 77 6f 72 | 64 73 20 28 65 76 65 6e |or 2 wor|ds (even|
|000018d0| 20 70 61 72 69 74 79 29 | 2e 0d 0d 20 20 20 20 6d | parity)|... m|
|000018e0| 61 70 57 69 64 74 68 3d | 28 33 32 2b 78 49 6e 64 |apWidth=|(32+xInd|
|000018f0| 65 78 4d 61 78 29 20 3e | 3e 20 35 3b 0d 20 20 20 |exMax) >|> 5;. |
|00001900| 20 6d 61 70 53 69 7a 65 | 3d 6d 61 70 57 69 64 74 | mapSize|=mapWidt|
|00001910| 68 2a 28 79 49 6e 64 65 | 78 4d 61 78 2b 31 29 3b |h*(yInde|xMax+1);|
|00001920| 0d 20 20 20 20 69 66 20 | 28 30 3d 3d 28 76 69 78 |. if |(0==(vix|
|00001930| 65 6c 4d 61 70 3d 0d 20 | 20 20 20 20 20 20 28 6c |elMap=. | (l|
|00001940| 6f 6e 67 2a 29 6d 61 6c | 6c 6f 63 28 32 2a 6d 61 |ong*)mal|loc(2*ma|
|00001950| 70 53 69 7a 65 2a 73 69 | 7a 65 6f 66 28 6c 6f 6e |pSize*si|zeof(lon|
|00001960| 67 29 29 29 29 20 72 65 | 74 75 72 6e 3b 0d 20 20 |g)))) re|turn;. |
|00001970| 20 20 69 66 20 28 6f 64 | 64 50 61 72 69 74 79 29 | if (od|dParity)|
|00001980| 20 6d 65 6d 73 65 74 28 | 76 69 78 65 6c 4d 61 70 | memset(|vixelMap|
|00001990| 2c 30 2c 6d 61 70 53 69 | 7a 65 2a 73 69 7a 65 6f |,0,mapSi|ze*sizeo|
|000019a0| 66 28 6c 6f 6e 67 29 29 | 3b 0d 20 20 20 20 65 6c |f(long))|;. el|
|000019b0| 73 65 20 6d 65 6d 73 65 | 74 28 76 69 78 65 6c 4d |se memse|t(vixelM|
|000019c0| 61 70 2c 30 2c 32 2a 6d | 61 70 53 69 7a 65 2a 73 |ap,0,2*m|apSize*s|
|000019d0| 69 7a 65 6f 66 28 6c 6f | 6e 67 29 29 3b 0d 0d 2f |izeof(lo|ng));../|
|000019e0| 2f 20 20 57 69 74 68 20 | 6f 64 64 20 70 61 72 69 |/ With |odd pari|
|000019f0| 74 79 2c 20 69 74 20 69 | 73 20 6f 6e 6c 79 20 6e |ty, it i|s only n|
|00001a00| 65 63 65 73 73 61 72 79 | 20 74 6f 20 58 4f 52 20 |ecessary| to XOR |
|00001a10| 74 68 65 20 76 69 78 65 | 6c 73 0d 2f 2f 20 20 6f |the vixe|ls.// o|
|00001a20| 66 20 61 6c 6c 20 69 6e | 70 75 74 20 72 65 63 74 |f all in|put rect|
|00001a30| 73 20 28 50 61 69 6e 74 | 4f 64 64 29 2e 0d 0d 2f |s (Paint|Odd).../|
|00001a40| 2f 20 20 57 69 74 68 20 | 65 76 65 6e 20 70 61 72 |/ With |even par|
|00001a50| 69 74 79 2c 20 77 65 20 | 61 6c 73 6f 20 6e 65 65 |ity, we |also nee|
|00001a60| 64 20 74 6f 20 4f 52 20 | 61 6c 6c 20 76 69 78 65 |d to OR |all vixe|
|00001a70| 6c 73 2e 20 20 54 68 69 | 73 0d 2f 2f 20 20 69 73 |ls. Thi|s.// is|
|00001a80| 20 64 6f 6e 65 20 69 6e | 20 74 68 65 20 61 6c 74 | done in| the alt|
|00001a90| 65 72 6e 61 74 65 20 77 | 6f 72 64 73 20 6f 66 20 |ernate w|ords of |
|00001aa0| 76 69 78 65 6c 4d 61 70 | 20 28 50 61 69 6e 74 45 |vixelMap| (PaintE|
|00001ab0| 76 65 6e 29 3b 0d 2f 2f | 20 20 68 65 6e 63 65 20 |ven);.//| hence |
|00001ac0| 74 68 65 20 76 69 78 65 | 6c 4d 61 70 20 69 73 20 |the vixe|lMap is |
|00001ad0| 73 74 72 65 74 63 68 65 | 64 20 77 69 74 68 20 65 |stretche|d with e|
|00001ae0| 76 65 6e 20 70 61 72 69 | 74 79 2e 0d 0d 2f 2f 20 |ven pari|ty...// |
|00001af0| 20 41 63 63 75 6d 75 6c | 61 74 65 20 74 68 65 20 | Accumul|ate the |
|00001b00| 65 6e 63 6c 6f 73 65 64 | 20 76 69 78 65 6c 73 20 |enclosed| vixels |
|00001b10| 6f 66 20 65 61 63 68 20 | 69 6e 70 75 74 20 72 65 |of each |input re|
|00001b20| 63 74 3a 0d 0d 20 20 20 | 20 66 6f 72 20 28 69 3d |ct:.. | for (i=|
|00001b30| 30 3b 69 3c 6e 75 6d 52 | 65 63 74 73 49 6e 3b 69 |0;i<numR|ectsIn;i|
|00001b40| 2b 2b 29 20 7b 0d 20 20 | 20 20 20 20 6c 6f 6e 67 |++) {. | long|
|00001b50| 20 20 54 2c 4c 2c 42 2c | 52 2c 78 2c 79 3b 0d 20 | T,L,B,|R,x,y;. |
|00001b60| 20 20 20 20 20 6c 6f 6e | 67 2a 20 76 6d 3b 0d 20 | lon|g* vm;. |
|00001b70| 20 20 20 20 20 54 3d 47 | 65 74 49 6e 64 65 78 28 | T=G|etIndex(|
|00001b80| 79 49 6e 64 65 78 4d 61 | 78 2c 79 49 6e 64 65 78 |yIndexMa|x,yIndex|
|00001b90| 2c 49 52 54 29 3b 0d 20 | 20 20 20 20 20 4c 3d 47 |,IRT);. | L=G|
|00001ba0| 65 74 49 6e 64 65 78 28 | 78 49 6e 64 65 78 4d 61 |etIndex(|xIndexMa|
|00001bb0| 78 2c 78 49 6e 64 65 78 | 2c 49 52 4c 29 3b 0d 20 |x,xIndex|,IRL);. |
|00001bc0| 20 20 20 20 20 42 3d 47 | 65 74 49 6e 64 65 78 28 | B=G|etIndex(|
|00001bd0| 79 49 6e 64 65 78 4d 61 | 78 2c 79 49 6e 64 65 78 |yIndexMa|x,yIndex|
|00001be0| 2c 49 52 42 29 3b 0d 20 | 20 20 20 20 20 52 3d 47 |,IRB);. | R=G|
|00001bf0| 65 74 49 6e 64 65 78 28 | 78 49 6e 64 65 78 4d 61 |etIndex(|xIndexMa|
|00001c00| 78 2c 78 49 6e 64 65 78 | 2c 49 52 52 29 3b 0d 20 |x,xIndex|,IRR);. |
|00001c10| 20 20 20 20 20 69 66 20 | 28 6f 64 64 50 61 72 69 | if |(oddPari|
|00001c20| 74 79 29 20 7b 0d 20 20 | 20 20 20 20 20 20 76 6d |ty) {. | vm|
|00001c30| 3d 76 69 78 65 6c 4d 61 | 70 2b 6d 61 70 57 69 64 |=vixelMa|p+mapWid|
|00001c40| 74 68 2a 54 2b 28 4c 3e | 3e 35 29 3b 0d 20 20 20 |th*T+(L>|>5);. |
|00001c50| 20 20 20 20 20 50 61 69 | 6e 74 4f 64 64 28 76 6d | Pai|ntOdd(vm|
|00001c60| 2c 42 2d 54 2c 4c 2c 52 | 2d 31 2c 6d 61 70 57 69 |,B-T,L,R|-1,mapWi|
|00001c70| 64 74 68 29 3b 0d 20 20 | 20 20 20 20 7d 20 65 6c |dth);. | } el|
|00001c80| 73 65 20 7b 0d 20 20 20 | 20 20 20 20 20 76 6d 3d |se {. | vm=|
|00001c90| 76 69 78 65 6c 4d 61 70 | 2b 32 2a 28 6d 61 70 57 |vixelMap|+2*(mapW|
|00001ca0| 69 64 74 68 2a 54 2b 28 | 4c 3e 3e 35 29 29 3b 0d |idth*T+(|L>>5));.|
|00001cb0| 20 20 20 20 20 20 20 20 | 50 61 69 6e 74 45 76 65 | |PaintEve|
|00001cc0| 6e 28 76 6d 2c 42 2d 54 | 2c 4c 2c 52 2d 31 2c 6d |n(vm,B-T|,L,R-1,m|
|00001cd0| 61 70 57 69 64 74 68 29 | 3b 0d 20 20 20 20 20 20 |apWidth)|;. |
|00001ce0| 7d 0d 20 20 20 20 7d 0d | 0d 2f 2f 20 20 46 6f 72 |}. }.|.// For|
|00001cf0| 20 65 76 65 6e 20 70 61 | 72 69 74 79 2c 20 58 4f | even pa|rity, XO|
|00001d00| 52 20 61 6c 6c 20 70 61 | 69 72 73 20 6f 66 20 77 |R all pa|irs of w|
|00001d10| 6f 72 64 73 20 69 6e 20 | 74 68 65 20 76 69 78 65 |ords in |the vixe|
|00001d20| 6c 4d 61 70 0d 2f 2f 20 | 20 74 6f 20 70 61 63 6b |lMap.// | to pack|
|00001d30| 20 69 74 20 69 6e 74 6f | 20 74 68 65 20 73 61 6d | it into| the sam|
|00001d40| 65 20 66 6f 72 6d 61 74 | 20 61 73 20 74 68 65 20 |e format| as the |
|00001d50| 6f 64 64 20 70 61 72 69 | 74 79 0d 2f 2f 20 20 76 |odd pari|ty.// v|
|00001d60| 69 78 65 6c 4d 61 70 2e | 0d 0d 20 20 20 20 69 66 |ixelMap.|.. if|
|00001d70| 20 28 21 6f 64 64 50 61 | 72 69 74 79 29 20 50 61 | (!oddPa|rity) Pa|
|00001d80| 63 6b 4d 61 70 28 76 69 | 78 65 6c 4d 61 70 2c 6d |ckMap(vi|xelMap,m|
|00001d90| 61 70 53 69 7a 65 29 3b | 0d 0d 2f 2f 20 20 4e 6f |apSize);|..// No|
|00001da0| 77 20 74 68 65 20 76 69 | 78 65 6c 4d 61 70 20 28 |w the vi|xelMap (|
|00001db0| 74 68 65 20 62 69 74 6d | 61 70 20 6f 66 20 61 6c |the bitm|ap of al|
|00001dc0| 6c 20 76 69 78 65 6c 73 | 2c 20 74 68 61 74 20 69 |l vixels|, that i|
|00001dd0| 73 0d 2f 2f 20 20 61 72 | 65 61 73 20 6f 66 20 74 |s.// ar|eas of t|
|00001de0| 68 65 20 73 63 72 65 65 | 6e 29 2c 20 69 73 20 73 |he scree|n), is s|
|00001df0| 65 74 20 74 6f 20 31 20 | 66 6f 72 20 65 76 65 72 |et to 1 |for ever|
|00001e00| 79 20 76 69 78 65 6c 0d | 2f 2f 20 20 6d 65 65 74 |y vixel.|// meet|
|00001e10| 69 6e 67 20 74 68 65 20 | 63 72 69 74 65 72 69 61 |ing the |criteria|
|00001e20| 20 6f 66 20 65 69 74 68 | 65 72 20 6f 64 64 20 6f | of eith|er odd o|
|00001e30| 72 20 65 76 65 6e 20 70 | 61 72 69 74 79 2e 0d 0d |r even p|arity...|
|00001e40| 2f 2f 20 20 57 65 20 73 | 63 61 6e 20 74 68 65 20 |// We s|can the |
|00001e50| 76 69 78 65 6c 20 6d 61 | 70 20 74 6f 20 66 69 6e |vixel ma|p to fin|
|00001e60| 64 20 63 6f 6e 74 69 67 | 75 6f 75 73 20 72 65 67 |d contig|uous reg|
|00001e70| 69 6f 6e 73 20 6f 66 0d | 2f 2f 20 20 6e 6f 6e 2d |ions of.|// non-|
|00001e80| 7a 65 72 6f 20 76 69 78 | 65 6c 73 20 69 6e 20 6f |zero vix|els in o|
|00001e90| 72 64 65 72 20 74 6f 20 | 67 65 6e 65 72 61 74 65 |rder to |generate|
|00001ea0| 20 74 68 65 20 6f 75 74 | 70 75 74 0d 2f 2f 20 20 | the out|put.// |
|00001eb0| 72 65 63 74 61 6e 67 6c | 65 73 2e 20 20 46 6f 72 |rectangl|es. For|
|00001ec0| 20 65 61 63 68 20 72 6f | 77 2c 20 77 65 20 73 75 | each ro|w, we su|
|00001ed0| 63 63 65 73 73 69 76 65 | 6c 79 20 6c 6f 6f 6b 20 |ccessive|ly look |
|00001ee0| 66 6f 72 0d 2f 2f 20 20 | 62 6c 6f 63 6b 73 20 6f |for.// |blocks o|
|00001ef0| 66 20 73 65 74 20 76 69 | 78 65 6c 73 2e 20 54 68 |f set vi|xels. Th|
|00001f00| 69 73 20 77 69 6c 6c 20 | 64 65 66 69 6e 65 20 6f |is will |define o|
|00001f10| 6e 65 20 6f 75 74 70 75 | 74 20 72 65 63 74 2e 0d |ne outpu|t rect..|
|00001f20| 2f 2f 20 20 54 68 65 20 | 58 2f 59 20 69 6e 64 65 |// The |X/Y inde|
|00001f30| 78 20 61 72 72 61 79 73 | 20 73 65 72 76 65 20 74 |x arrays| serve t|
|00001f40| 6f 20 63 6f 6e 76 65 72 | 74 20 74 68 65 20 76 69 |o conver|t the vi|
|00001f50| 78 65 6c 0d 2f 2f 20 20 | 63 6f 6f 72 64 69 6e 61 |xel.// |coordina|
|00001f60| 74 65 73 20 62 61 63 6b | 20 74 6f 20 74 68 65 20 |tes back| to the |
|00001f70| 72 65 61 6c 20 70 69 78 | 65 6c 20 63 6f 6f 72 64 |real pix|el coord|
|00001f80| 69 6e 61 74 65 73 20 77 | 68 69 63 68 0d 2f 2f 20 |inates w|hich.// |
|00001f90| 20 64 65 66 69 6e 65 20 | 74 68 65 20 6f 75 74 70 | define |the outp|
|00001fa0| 75 74 20 72 65 63 74 61 | 6e 67 6c 65 73 2e 0d 0d |ut recta|ngles...|
|00001fb0| 20 20 7b 20 6c 6f 6e 67 | 20 77 6f 72 64 2c 62 69 | { long| word,bi|
|00001fc0| 74 2c 62 62 2c 63 2c 75 | 2c 4c 2c 42 3b 0d 20 20 |t,bb,c,u|,L,B;. |
|00001fd0| 20 20 6c 6f 6e 67 2a 20 | 76 6d 3d 76 69 78 65 6c | long* |vm=vixel|
|00001fe0| 4d 61 70 3b 0d 20 20 20 | 20 66 6f 72 20 28 69 3d |Map;. | for (i=|
|00001ff0| 30 3b 69 3c 79 49 6e 64 | 65 78 4d 61 78 3b 69 2b |0;i<yInd|exMax;i+|
|00002000| 2b 29 20 7b 0d 20 20 20 | 20 20 20 62 69 74 3d 30 |+) {. | bit=0|
|00002010| 3b 0d 20 20 20 20 20 20 | 63 3d 30 3b 0d 20 20 20 |;. |c=0;. |
|00002020| 20 20 20 66 6f 72 20 28 | 77 6f 72 64 3d 30 3b 77 | for (|word=0;w|
|00002030| 6f 72 64 3c 6d 61 70 57 | 69 64 74 68 3b 77 6f 72 |ord<mapW|idth;wor|
|00002040| 64 2b 2b 29 20 7b 0d 20 | 20 20 20 20 20 20 20 75 |d++) {. | u|
|00002050| 3d 76 6d 5b 77 6f 72 64 | 5d 3b 63 3d 30 3b 0d 20 |=vm[word|];c=0;. |
|00002060| 20 20 20 20 20 20 20 69 | 66 20 28 75 29 20 7b 0d | i|f (u) {.|
|00002070| 20 20 20 20 20 20 20 20 | 20 20 6c 6f 6e 67 2a 20 | | long* |
|00002080| 76 6d 42 65 6c 6f 77 3d | 76 6d 2b 77 6f 72 64 2b |vmBelow=|vm+word+|
|00002090| 6d 61 70 57 69 64 74 68 | 3b 0d 20 20 20 20 20 20 |mapWidth|;. |
|000020a0| 20 20 20 20 62 62 3d 30 | 3b 0d 20 20 20 20 20 20 | bb=0|;. |
|000020b0| 20 20 20 20 64 6f 20 7b | 0d 20 20 20 20 20 20 20 | do {|. |
|000020c0| 20 20 20 20 20 77 68 69 | 6c 65 20 28 75 3e 30 29 | whi|le (u>0)|
|000020d0| 20 7b 62 62 2b 2b 3b 75 | 3c 3c 3d 31 3b 7d 0d 20 | {bb++;u|<<=1;}. |
|000020e0| 20 20 20 20 20 20 20 20 | 20 20 20 69 66 20 28 63 | | if (c|
|000020f0| 3d 3d 30 29 20 7b 0d 20 | 20 20 20 20 20 20 20 20 |==0) {. | |
|00002100| 20 20 20 20 20 4c 3d 62 | 62 3b 0d 20 20 20 20 20 | L=b|b;. |
|00002110| 20 20 20 20 20 20 20 20 | 20 4f 52 4c 3d 78 49 6e | | ORL=xIn|
|00002120| 64 65 78 5b 62 69 74 2b | 4c 5d 3b 20 63 2d 2d 3b |dex[bit+|L]; c--;|
|00002130| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 7d 20 65 |. | } e|
|00002140| 6c 73 65 20 7b 0d 20 20 | 20 20 20 20 20 20 20 20 |lse {. | |
|00002150| 20 20 20 20 6c 6f 6e 67 | 2a 20 76 6d 78 3d 76 6d | long|* vmx=vm|
|00002160| 42 65 6c 6f 77 3b 0d 20 | 20 20 20 20 20 20 20 20 |Below;. | |
|00002170| 20 20 20 20 20 6c 6f 6e | 67 20 6d 61 73 6b 3d 7e | lon|g mask=~|
|00002180| 28 6c 65 66 74 4d 61 73 | 6b 5b 4c 5d 20 26 20 72 |(leftMas|k[L] & r|
|00002190| 69 67 68 74 4d 61 73 6b | 5b 62 62 2d 31 5d 29 3b |ightMask|[bb-1]);|
|000021a0| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 42 |. | B|
|000021b0| 3d 69 2b 31 3b 0d 2f 2f | 44 65 66 61 75 6c 74 3a |=i+1;.//|Default:|
|000021c0| 20 74 68 65 20 72 65 63 | 74 61 6e 67 6c 65 20 69 | the rec|tangle i|
|000021d0| 73 20 31 20 76 69 78 65 | 6c 20 68 69 67 68 2e 0d |s 1 vixe|l high..|
|000021e0| 2f 2f 57 65 20 74 72 79 | 20 74 6f 20 65 78 74 65 |//We try| to exte|
|000021f0| 6e 64 20 72 65 63 74 61 | 6e 67 6c 65 20 64 6f 77 |nd recta|ngle dow|
|00002200| 6e 20 61 73 20 66 61 72 | 20 61 73 20 70 6f 73 73 |n as far| as poss|
|00002210| 69 62 6c 65 3a 0d 20 20 | 20 20 20 20 20 20 20 20 |ible:. | |
|00002220| 20 20 20 20 77 68 69 6c | 65 20 28 2d 31 3d 3d 28 | whil|e (-1==(|
|00002230| 6d 61 73 6b 20 7c 20 2a | 76 6d 78 29 29 20 7b 0d |mask | *|vmx)) {.|
|00002240| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002250| 42 2b 2b 3b 2a 76 6d 78 | 20 26 3d 20 6d 61 73 6b |B++;*vmx| &= mask|
|00002260| 3b 76 6d 78 2b 3d 6d 61 | 70 57 69 64 74 68 3b 0d |;vmx+=ma|pWidth;.|
|00002270| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 7d 0d | | }.|
|00002280| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 4f 52 | | OR|
|00002290| 42 3d 79 49 6e 64 65 78 | 5b 42 5d 3b 0d 20 20 20 |B=yIndex|[B];. |
|000022a0| 20 20 20 20 20 20 20 20 | 20 20 20 4f 52 52 3d 78 | | ORR=x|
|000022b0| 49 6e 64 65 78 5b 62 69 | 74 2b 62 62 5d 3b 0d 20 |Index[bi|t+bb];. |
|000022c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 4f 52 54 | | ORT|
|000022d0| 3d 79 49 6e 64 65 78 5b | 69 5d 3b 0d 20 20 20 20 |=yIndex[|i];. |
|000022e0| 20 20 20 20 20 20 20 20 | 20 20 4f 52 70 74 72 2b | | ORptr+|
|000022f0| 2b 3b 0d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |+;. | |
|00002300| 20 63 3d 30 3b 0d 20 20 | 20 20 20 20 20 20 20 20 | c=0;. | |
|00002310| 20 20 7d 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 | }. | |
|00002320| 69 66 20 28 30 3d 3d 28 | 75 3d 28 7e 75 29 20 26 |if (0==(|u=(~u) &|
|00002330| 20 72 69 67 68 74 4d 61 | 73 6b 5b 33 31 2d 62 62 | rightMa|sk[31-bb|
|00002340| 5d 29 29 20 62 72 65 61 | 6b 3b 0d 20 20 20 20 20 |])) brea|k;. |
|00002350| 20 20 20 20 20 7d 20 77 | 68 69 6c 65 28 62 62 3c | } w|hile(bb<|
|00002360| 33 32 29 3b 0d 20 20 20 | 20 20 20 20 20 20 20 69 |32);. | i|
|00002370| 66 20 28 63 29 20 7b 0d | 20 20 20 20 20 20 20 20 |f (c) {.| |
|00002380| 20 20 20 20 6c 6f 6e 67 | 2a 20 76 6d 78 3d 76 6d | long|* vmx=vm|
|00002390| 42 65 6c 6f 77 3b 0d 20 | 20 20 20 20 20 20 20 20 |Below;. | |
|000023a0| 20 20 20 6c 6f 6e 67 20 | 6d 61 73 6b 3d 7e 6c 65 | long |mask=~le|
|000023b0| 66 74 4d 61 73 6b 5b 4c | 5d 3b 0d 20 20 20 20 20 |ftMask[L|];. |
|000023c0| 20 20 20 20 20 20 20 42 | 3d 69 2b 31 3b 0d 20 20 | B|=i+1;. |
|000023d0| 20 20 20 20 20 20 20 20 | 20 20 77 68 69 6c 65 20 | | while |
|000023e0| 28 2d 31 3d 3d 28 6d 61 | 73 6b 20 7c 20 2a 76 6d |(-1==(ma|sk | *vm|
|000023f0| 78 29 29 20 7b 0d 20 20 | 20 20 20 20 20 20 20 20 |x)) {. | |
|00002400| 20 20 20 20 42 2b 2b 3b | 2a 76 6d 78 20 26 3d 20 | B++;|*vmx &= |
|00002410| 6d 61 73 6b 3b 76 6d 78 | 2b 3d 6d 61 70 57 69 64 |mask;vmx|+=mapWid|
|00002420| 74 68 3b 0d 20 20 20 20 | 20 20 20 20 20 20 20 20 |th;. | |
|00002430| 7d 0d 20 20 20 20 20 20 | 20 20 20 20 20 20 4f 52 |}. | OR|
|00002440| 42 3d 79 49 6e 64 65 78 | 5b 42 5d 3b 0d 20 20 20 |B=yIndex|[B];. |
|00002450| 20 20 20 20 20 20 20 20 | 20 4f 52 52 3d 78 49 6e | | ORR=xIn|
|00002460| 64 65 78 5b 62 69 74 2b | 33 32 5d 3b 0d 20 20 20 |dex[bit+|32];. |
|00002470| 20 20 20 20 20 20 20 20 | 20 4f 52 54 3d 79 49 6e | | ORT=yIn|
|00002480| 64 65 78 5b 69 5d 3b 0d | 20 20 20 20 20 20 20 20 |dex[i];.| |
|00002490| 20 20 20 20 4f 52 70 74 | 72 2b 2b 3b 0d 20 20 20 | ORpt|r++;. |
|000024a0| 20 20 20 20 20 20 20 7d | 0d 20 20 20 20 20 20 20 | }|. |
|000024b0| 20 7d 0d 20 20 20 20 20 | 20 20 20 62 69 74 2b 3d | }. | bit+=|
|000024c0| 33 32 3b 0d 20 20 20 20 | 20 20 7d 0d 20 20 20 20 |32;. | }. |
|000024d0| 20 20 76 6d 2b 3d 6d 61 | 70 57 69 64 74 68 3b 0d | vm+=ma|pWidth;.|
|000024e0| 20 20 20 20 7d 0d 0d 20 | 20 7d 0d 20 20 66 72 65 | }.. | }. fre|
|000024f0| 65 28 79 48 65 61 70 29 | 3b 20 20 20 20 20 20 20 |e(yHeap)|; |
|00002500| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2f 66 72 65 | | //fre|
|00002510| 65 20 61 6c 6c 6f 63 61 | 74 65 64 20 6d 65 6d 6f |e alloca|ted memo|
|00002520| 72 79 0d 20 20 66 72 65 | 65 28 76 69 78 65 6c 4d |ry. fre|e(vixelM|
|00002530| 61 70 29 3b 0d 20 20 2a | 6e 75 6d 52 65 63 74 73 |ap);. *|numRects|
|00002540| 4f 75 74 3d 4f 52 70 74 | 72 2d 6f 75 74 70 75 74 |Out=ORpt|r-output|
|00002550| 52 65 63 74 73 3b 0d 7d | 0d 0d 2f 2f 2f 2f 2f 2f |Rects;.}|..//////|
|00002560| 2f 2f 2f 2f 2f 2f 2f 2f | 2f 2f 2f 2f 2f 2f 2f 2f |////////|////////|
|00002570| 2f 2f 2f 2f 2f 2f 2f 2f | 2f 2f 2f 2f 2f 2f 2f 2f |////////|////////|
|00002580| 2f 2f 2f 2f 2f 2f 2f 2f | 2f 2f 2f 2f 2f 2f 2f 2f |////////|////////|
|00002590| 2f 2f 2f 2f 2f 0d 2f 2f | 20 41 75 78 69 6c 69 61 |/////.//| Auxilia|
|000025a0| 72 79 20 66 75 6e 63 74 | 69 6f 6e 73 20 63 61 6c |ry funct|ions cal|
|000025b0| 6c 65 64 20 62 79 20 52 | 65 63 74 61 6e 67 6c 65 |led by R|ectangle|
|000025c0| 49 6e 74 65 72 73 65 63 | 74 69 6f 6e 73 3a 20 2f |Intersec|tions: /|
|000025d0| 2f 0d 2f 2f 2f 2f 2f 2f | 2f 2f 2f 2f 2f 2f 2f 2f |/.//////|////////|
|000025e0| 2f 2f 2f 2f 2f 2f 2f 2f | 2f 2f 2f 2f 2f 2f 2f 2f |////////|////////|
|000025f0| 2f 2f 2f 2f 2f 2f 2f 2f | 2f 2f 2f 2f 2f 2f 2f 2f |////////|////////|
|00002600| 2f 2f 2f 2f 2f 2f 2f 2f | 2f 2f 2f 2f 2f 0d 0d 2f |////////|/////../|
|00002610| 2a 20 49 6e 73 65 72 74 | 20 67 72 6f 77 73 20 61 |* Insert| grows a|
|00002620| 20 68 65 61 70 2c 20 74 | 68 61 74 20 69 73 20 61 | heap, t|hat is a|
|00002630| 20 70 61 72 74 69 61 6c | 6c 79 20 73 6f 72 74 65 | partial|ly sorte|
|00002640| 64 20 62 61 6c 61 6e 63 | 65 64 0d 20 20 20 62 69 |d balanc|ed. bi|
|00002650| 6e 61 72 79 20 74 72 65 | 65 2c 20 77 68 65 72 65 |nary tre|e, where|
|00002660| 20 65 61 63 68 20 6e 6f | 64 65 27 73 20 63 68 69 | each no|de's chi|
|00002670| 6c 64 72 65 6e 20 6d 75 | 73 74 20 62 65 20 6c 65 |ldren mu|st be le|
|00002680| 73 73 20 6f 72 0d 20 20 | 20 65 71 75 61 6c 2c 20 |ss or. | equal, |
|00002690| 62 75 74 20 6e 6f 74 20 | 69 6e 20 61 6e 79 20 70 |but not |in any p|
|000026a0| 61 72 74 69 63 75 6c 61 | 72 20 6f 72 64 65 72 2e |articula|r order.|
|000026b0| 0d 0d 20 20 20 45 61 63 | 68 20 76 61 6c 75 65 20 |.. Eac|h value |
|000026c0| 78 20 69 73 20 69 6e 73 | 65 72 74 65 64 20 62 79 |x is ins|erted by|
|000026d0| 20 61 70 70 65 6e 64 69 | 6e 67 20 69 74 20 61 73 | appendi|ng it as|
|000026e0| 20 74 68 65 20 6c 61 73 | 74 20 6e 6f 64 65 0d 20 | the las|t node. |
|000026f0| 20 20 61 6e 64 20 74 68 | 65 6e 20 73 69 66 74 69 | and th|en sifti|
|00002700| 6e 67 20 69 74 20 75 70 | 20 28 65 78 63 68 61 6e |ng it up| (exchan|
|00002710| 67 69 6e 67 20 66 61 74 | 68 65 72 20 61 6e 64 20 |ging fat|her and |
|00002720| 63 68 69 6c 64 0d 20 20 | 20 6e 6f 64 65 73 29 20 |child. | nodes) |
|00002730| 75 6e 74 69 6c 20 74 68 | 65 20 68 65 61 70 20 70 |until th|e heap p|
|00002740| 72 6f 70 65 72 74 79 20 | 69 73 20 72 65 73 74 6f |roperty |is resto|
|00002750| 72 65 64 2e 0d 2a 2f 0d | 76 6f 69 64 20 49 6e 73 |red..*/.|void Ins|
|00002760| 65 72 74 28 6c 6f 6e 67 | 2a 20 68 2c 6c 6f 6e 67 |ert(long|* h,long|
|00002770| 20 73 69 7a 65 2c 6c 6f | 6e 67 20 78 29 20 7b 0d | size,lo|ng x) {.|
|00002780| 20 20 6c 6f 6e 67 20 69 | 2c 6a 2c 7a 3b 0d 20 20 | long i|,j,z;. |
|00002790| 69 3d 73 69 7a 65 3b 0d | 20 20 64 6f 20 7b 0d 20 |i=size;.| do {. |
|000027a0| 20 20 20 6a 3d 69 3e 3e | 31 3b 0d 20 20 20 20 69 | j=i>>|1;. i|
|000027b0| 66 20 28 78 3c 3d 28 7a | 3d 68 5b 6a 5d 29 29 20 |f (x<=(z|=h[j])) |
|000027c0| 62 72 65 61 6b 3b 0d 20 | 20 20 20 68 5b 69 5d 3d |break;. | h[i]=|
|000027d0| 7a 3b 0d 20 20 20 20 69 | 3d 6a 3b 0d 20 20 7d 20 |z;. i|=j;. } |
|000027e0| 77 68 69 6c 65 28 31 29 | 3b 0d 20 20 68 5b 69 5d |while(1)|;. h[i]|
|000027f0| 3d 78 3b 0d 7d 0d 0d 2f | 2a 20 54 68 65 20 68 65 |=x;.}../|* The he|
|00002800| 61 70 20 6b 65 65 70 73 | 20 74 68 65 20 6c 61 72 |ap keeps| the lar|
|00002810| 67 65 73 74 20 76 61 6c | 75 65 20 61 74 20 74 68 |gest val|ue at th|
|00002820| 65 20 72 6f 6f 74 2c 20 | 61 74 20 68 5b 31 5d 2e |e root, |at h[1].|
|00002830| 0d 20 20 20 57 65 20 73 | 6f 72 74 20 61 73 20 66 |. We s|ort as f|
|00002840| 6f 6c 6c 6f 77 73 3a 20 | 65 61 63 68 20 72 6f 6f |ollows: |each roo|
|00002850| 74 20 76 61 6c 75 65 20 | 69 73 20 72 65 6d 6f 76 |t value |is remov|
|00002860| 65 64 20 61 6e 64 20 70 | 75 74 0d 20 20 20 61 74 |ed and p|ut. at|
|00002870| 20 74 68 65 20 65 6e 64 | 20 6f 66 20 74 68 65 20 | the end| of the |
|00002880| 61 72 72 61 79 3b 20 20 | 74 68 65 6e 20 74 68 65 |array; |then the|
|00002890| 20 6c 61 73 74 20 69 74 | 65 6d 20 69 6e 20 74 68 | last it|em in th|
|000028a0| 65 20 68 65 61 70 0d 20 | 20 20 69 73 20 70 75 74 |e heap. | is put|
|000028b0| 20 69 6e 74 6f 20 74 68 | 65 20 72 6f 6f 74 20 61 | into th|e root a|
|000028c0| 6e 64 20 73 69 66 74 65 | 64 20 64 6f 77 6e 20 75 |nd sifte|d down u|
|000028d0| 6e 74 69 6c 20 74 68 65 | 20 68 65 61 70 0d 20 20 |ntil the| heap. |
|000028e0| 20 70 72 6f 70 65 72 74 | 79 20 69 73 20 72 65 73 | propert|y is res|
|000028f0| 74 6f 72 65 64 2e 0d 20 | 20 20 57 68 65 6e 20 77 |tored.. | When w|
|00002900| 65 20 61 72 65 20 64 6f | 6e 65 2c 20 74 68 65 20 |e are do|ne, the |
|00002910| 61 72 72 61 79 20 69 73 | 20 73 6f 72 74 65 64 2e |array is| sorted.|
|00002920| 0d 20 20 20 41 73 20 77 | 65 20 67 6f 20 61 6c 6f |. As w|e go alo|
|00002930| 6e 67 2c 20 77 65 20 72 | 65 63 6f 67 6e 69 7a 65 |ng, we r|ecognize|
|00002940| 20 64 75 70 6c 69 63 61 | 74 65 20 76 61 6c 75 65 | duplica|te value|
|00002950| 73 20 61 6e 64 20 72 65 | 6d 6f 76 65 0d 20 20 20 |s and re|move. |
|00002960| 74 68 65 6d 20 62 75 74 | 20 64 6f 20 6e 6f 74 20 |them but| do not |
|00002970| 70 75 74 20 74 68 65 6d | 20 62 61 63 6b 2e 20 20 |put them| back. |
|00002980| 54 68 65 20 72 65 73 75 | 6c 74 20 69 73 20 74 68 |The resu|lt is th|
|00002990| 61 74 20 74 68 65 0d 20 | 20 20 73 74 61 72 74 20 |at the. | start |
|000029a0| 6f 66 20 74 68 65 20 73 | 6f 72 74 65 64 20 6c 69 |of the s|orted li|
|000029b0| 73 74 20 6d 61 79 20 62 | 65 20 66 75 72 74 68 65 |st may b|e furthe|
|000029c0| 72 20 75 70 20 69 6e 20 | 74 68 65 20 61 72 72 61 |r up in |the arra|
|000029d0| 79 2e 0d 2a 2f 0d 6c 6f | 6e 67 2a 20 53 6f 72 74 |y..*/.lo|ng* Sort|
|000029e0| 28 6c 6f 6e 67 2a 20 68 | 2c 6c 6f 6e 67 20 73 69 |(long* h|,long si|
|000029f0| 7a 65 29 20 7b 0d 20 20 | 6c 6f 6e 67 20 20 78 2c |ze) {. |long x,|
|00002a00| 7a 2c 69 2c 6a 3b 0d 20 | 20 6c 6f 6e 67 2a 20 62 |z,i,j;. | long* b|
|00002a10| 3d 68 2b 73 69 7a 65 2b | 31 3b 0d 20 20 2a 62 3d |=h+size+|1;. *b=|
|00002a20| 4d 41 58 4c 4f 4e 47 3b | 0d 20 20 69 66 20 28 73 |MAXLONG;|. if (s|
|00002a30| 69 7a 65 3e 31 29 20 64 | 6f 20 7b 0d 20 20 20 20 |ize>1) d|o {. |
|00002a40| 73 69 7a 65 2d 2d 3b 0d | 20 20 20 20 69 3d 31 3b |size--;.| i=1;|
|00002a50| 0d 20 20 20 20 6a 3d 32 | 3b 0d 20 20 20 20 69 66 |. j=2|;. if|
|00002a60| 20 28 2a 62 20 21 3d 20 | 28 7a 3d 68 5b 31 5d 29 | (*b != |(z=h[1])|
|00002a70| 29 20 2a 28 2d 2d 62 29 | 20 3d 20 7a 3b 0d 20 20 |) *(--b)| = z;. |
|00002a80| 20 20 69 66 20 28 73 69 | 7a 65 3c 3d 31 29 20 62 | if (si|ze<=1) b|
|00002a90| 72 65 61 6b 3b 0d 20 20 | 20 20 78 3d 68 5b 73 69 |reak;. | x=h[si|
|00002aa0| 7a 65 5d 3b 0d 20 20 20 | 20 68 5b 73 69 7a 65 5d |ze];. | h[size]|
|00002ab0| 3d 2d 4d 41 58 4c 4f 4e | 47 3b 0d 20 20 20 20 77 |=-MAXLON|G;. w|
|00002ac0| 68 69 6c 65 20 28 6a 3c | 73 69 7a 65 29 20 7b 0d |hile (j<|size) {.|
|00002ad0| 20 20 20 20 20 20 6c 6f | 6e 67 20 68 30 3d 68 5b | lo|ng h0=h[|
|00002ae0| 6a 5d 2c 68 31 3d 68 5b | 31 2b 6a 5d 3b 0d 20 20 |j],h1=h[|1+j];. |
|00002af0| 20 20 20 20 69 66 20 28 | 68 30 3c 68 31 29 20 7b | if (|h0<h1) {|
|00002b00| 6a 2b 2b 3b 20 68 30 3d | 68 31 3b 7d 0d 20 20 20 |j++; h0=|h1;}. |
|00002b10| 20 20 20 69 66 20 28 78 | 3e 3d 68 30 29 20 62 72 | if (x|>=h0) br|
|00002b20| 65 61 6b 3b 0d 20 20 20 | 20 20 20 68 5b 69 5d 3d |eak;. | h[i]=|
|00002b30| 68 30 3b 0d 20 20 20 20 | 20 20 69 3d 6a 3b 0d 20 |h0;. | i=j;. |
|00002b40| 20 20 20 20 20 6a 2b 3d | 6a 3b 0d 20 20 20 20 7d | j+=|j;. }|
|00002b50| 0d 20 20 20 20 68 5b 69 | 5d 3d 78 3b 0d 20 20 7d |. h[i|]=x;. }|
|00002b60| 20 77 68 69 6c 65 28 31 | 29 3b 0d 20 20 72 65 74 | while(1|);. ret|
|00002b70| 75 72 6e 20 62 3b 0d 7d | 0d 0d 2f 2a 20 47 65 74 |urn b;.}|../* Get|
|00002b80| 49 6e 64 65 78 20 75 73 | 65 73 20 61 20 62 69 6e |Index us|es a bin|
|00002b90| 61 72 79 20 73 65 61 72 | 63 68 20 74 6f 20 6c 6f |ary sear|ch to lo|
|00002ba0| 63 61 74 65 20 61 20 70 | 61 72 74 69 63 75 6c 61 |cate a p|articula|
|00002bb0| 72 0d 20 20 20 65 6e 74 | 72 79 20 61 6e 64 20 72 |r. ent|ry and r|
|00002bc0| 65 74 75 72 6e 73 20 69 | 74 73 20 69 6e 64 65 78 |eturns i|ts index|
|00002bd0| 2e 0d 2a 2f 0d 6c 6f 6e | 67 20 47 65 74 49 6e 64 |..*/.lon|g GetInd|
|00002be0| 65 78 28 6c 6f 6e 67 20 | 72 2c 6c 6f 6e 67 2a 20 |ex(long |r,long* |
|00002bf0| 69 6e 64 65 78 2c 6c 6f | 6e 67 20 7a 29 20 7b 0d |index,lo|ng z) {.|
|00002c00| 20 20 6c 6f 6e 67 20 6c | 3d 30 2c 6d 3d 72 3e 3e | long l|=0,m=r>>|
|00002c10| 31 2c 79 3b 0d 20 20 64 | 6f 20 7b 0d 20 20 20 20 |1,y;. d|o {. |
|00002c20| 69 66 20 28 7a 3e 28 79 | 3d 69 6e 64 65 78 5b 6d |if (z>(y|=index[m|
|00002c30| 5d 29 29 20 6c 3d 6d 2b | 31 3b 0d 20 20 20 20 65 |])) l=m+|1;. e|
|00002c40| 6c 73 65 20 69 66 20 28 | 7a 3c 79 29 20 20 20 20 |lse if (|z<y) |
|00002c50| 20 20 20 72 3d 6d 2d 31 | 3b 0d 20 20 20 20 65 6c | r=m-1|;. el|
|00002c60| 73 65 20 72 65 74 75 72 | 6e 20 6d 3b 0d 20 20 20 |se retur|n m;. |
|00002c70| 20 6d 3d 28 6c 2b 72 29 | 3e 3e 31 3b 0d 20 20 7d | m=(l+r)|>>1;. }|
|00002c80| 20 77 68 69 6c 65 20 28 | 6c 3c 72 29 3b 0d 20 20 | while (|l<r);. |
|00002c90| 72 65 74 75 72 6e 20 72 | 3b 0d 7d 0d 0d 0d 2f 2a |return r|;.}.../*|
|00002ca0| 20 54 68 65 20 50 61 69 | 6e 74 4f 64 64 20 61 6e | The Pai|ntOdd an|
|00002cb0| 64 20 50 61 69 6e 74 45 | 76 65 6e 20 72 6f 75 74 |d PaintE|ven rout|
|00002cc0| 69 6e 65 73 20 70 61 69 | 6e 74 20 72 65 63 74 61 |ines pai|nt recta|
|00002cd0| 6e 67 6c 65 73 0d 20 20 | 20 69 6e 74 6f 20 74 68 |ngles. | into th|
|00002ce0| 65 20 76 69 78 65 6c 20 | 6d 61 70 2e 0d 20 20 20 |e vixel |map.. |
|00002cf0| 50 61 69 6e 74 4f 64 64 | 20 6f 6e 6c 79 20 58 4f |PaintOdd| only XO|
|00002d00| 52 73 20 61 20 73 69 6e | 67 6c 65 20 62 69 74 20 |Rs a sin|gle bit |
|00002d10| 6d 61 70 20 77 69 74 68 | 20 61 20 72 65 63 74 61 |map with| a recta|
|00002d20| 6e 67 6c 65 2e 0d 20 20 | 20 50 61 69 6e 74 45 76 |ngle.. | PaintEv|
|00002d30| 65 6e 20 61 6c 73 6f 20 | 4f 52 73 20 61 20 73 65 |en also |ORs a se|
|00002d40| 63 6f 6e 64 20 62 69 74 | 20 6d 61 70 20 77 69 74 |cond bit| map wit|
|00002d50| 68 20 74 68 65 20 73 61 | 6d 65 0d 20 20 20 72 65 |h the sa|me. re|
|00002d60| 63 74 61 6e 67 6c 65 2e | 20 20 54 68 65 20 32 20 |ctangle.| The 2 |
|00002d70| 62 69 74 20 6d 61 70 73 | 20 61 72 65 20 77 6f 72 |bit maps| are wor|
|00002d80| 64 20 69 6e 74 65 72 6c | 65 61 76 65 64 2e 0d 20 |d interl|eaved.. |
|00002d90| 20 20 49 74 20 69 73 20 | 68 6f 70 65 64 20 74 68 | It is |hoped th|
|00002da0| 61 74 20 74 68 69 73 20 | 72 65 64 75 63 65 73 20 |at this |reduces |
|00002db0| 63 61 63 68 65 20 6d 69 | 73 73 65 73 20 62 79 20 |cache mi|sses by |
|00002dc0| 6b 65 65 70 69 6e 67 0d | 20 20 20 74 6f 20 6f 6e |keeping.| to on|
|00002dd0| 65 20 61 72 65 61 20 6f | 66 20 6d 65 6d 6f 72 79 |e area o|f memory|
|00002de0| 20 66 6f 72 20 65 61 63 | 68 20 72 6f 77 20 6f 66 | for eac|h row of|
|00002df0| 20 61 20 72 65 63 74 61 | 6e 67 6c 65 2e 0d 2a 2f | a recta|ngle..*/|
|00002e00| 0d 76 6f 69 64 20 20 50 | 61 69 6e 74 4f 64 64 28 |.void P|aintOdd(|
|00002e10| 6c 6f 6e 67 2a 20 76 6d | 2c 6c 6f 6e 67 20 48 2c |long* vm|,long H,|
|00002e20| 6c 6f 6e 67 20 4c 2c 6c | 6f 6e 67 20 52 2c 6c 6f |long L,l|ong R,lo|
|00002e30| 6e 67 20 6d 61 70 57 69 | 64 74 68 29 20 7b 0d 6c |ng mapWi|dth) {.l|
|00002e40| 6f 6e 67 20 4c 4d 3d 6c | 65 66 74 4d 61 73 6b 5b |ong LM=l|eftMask[|
|00002e50| 4c 20 26 20 33 31 5d 3b | 0d 6c 6f 6e 67 20 52 4d |L & 31];|.long RM|
|00002e60| 3d 72 69 67 68 74 4d 61 | 73 6b 5b 52 20 26 20 33 |=rightMa|sk[R & 3|
|00002e70| 31 5d 3b 0d 6c 6f 6e 67 | 20 6e 75 6d 4d 69 64 3d |1];.long| numMid=|
|00002e80| 28 52 3e 3e 35 29 2d 28 | 4c 3e 3e 35 29 2d 31 3b |(R>>5)-(|L>>5)-1;|
|00002e90| 0d 6c 6f 6e 67 20 78 2c | 79 2c 70 61 64 3d 6d 61 |.long x,|y,pad=ma|
|00002ea0| 70 57 69 64 74 68 2d 6e | 75 6d 4d 69 64 2d 32 3b |pWidth-n|umMid-2;|
|00002eb0| 0d 0d 20 20 69 66 20 28 | 6e 75 6d 4d 69 64 3c 30 |.. if (|numMid<0|
|00002ec0| 29 20 7b 4c 4d 26 3d 52 | 4d 3b 52 4d 3d 30 3b 7d |) {LM&=R|M;RM=0;}|
|00002ed0| 0d 0d 20 20 66 6f 72 20 | 28 79 3d 30 3b 79 3c 48 |.. for |(y=0;y<H|
|00002ee0| 3b 79 2b 2b 29 20 7b 0d | 20 20 20 20 2a 76 6d 20 |;y++) {.| *vm |
|00002ef0| 5e 3d 20 4c 4d 3b 20 76 | 6d 2b 2b 3b 0d 20 20 20 |^= LM; v|m++;. |
|00002f00| 20 66 6f 72 20 28 78 3d | 30 3b 78 3c 6e 75 6d 4d | for (x=|0;x<numM|
|00002f10| 69 64 3b 78 2b 2b 29 20 | 7b 0d 20 20 20 20 20 20 |id;x++) |{. |
|00002f20| 2a 76 6d 20 5e 3d 20 30 | 78 46 46 46 46 46 46 46 |*vm ^= 0|xFFFFFFF|
|00002f30| 46 3b 20 76 6d 2b 2b 3b | 0d 20 20 20 20 7d 0d 20 |F; vm++;|. }. |
|00002f40| 20 20 20 69 66 20 28 52 | 4d 29 20 7b 0d 20 20 20 | if (R|M) {. |
|00002f50| 20 20 20 2a 76 6d 20 5e | 3d 20 52 4d 3b 20 76 6d | *vm ^|= RM; vm|
|00002f60| 2b 2b 3b 0d 20 20 20 20 | 7d 0d 20 20 20 20 76 6d |++;. |}. vm|
|00002f70| 2b 3d 70 61 64 3b 0d 20 | 20 7d 0d 7d 0d 0d 76 6f |+=pad;. | }.}..vo|
|00002f80| 69 64 20 20 50 61 69 6e | 74 45 76 65 6e 20 28 6c |id Pain|tEven (l|
|00002f90| 6f 6e 67 2a 20 76 6d 2c | 6c 6f 6e 67 20 48 2c 6c |ong* vm,|long H,l|
|00002fa0| 6f 6e 67 20 4c 2c 6c 6f | 6e 67 20 52 2c 6c 6f 6e |ong L,lo|ng R,lon|
|00002fb0| 67 20 6d 61 70 57 69 64 | 74 68 29 20 7b 0d 6c 6f |g mapWid|th) {.lo|
|00002fc0| 6e 67 20 4c 4d 3d 6c 65 | 66 74 4d 61 73 6b 5b 4c |ng LM=le|ftMask[L|
|00002fd0| 20 26 20 33 31 5d 3b 0d | 6c 6f 6e 67 20 52 4d 3d | & 31];.|long RM=|
|00002fe0| 72 69 67 68 74 4d 61 73 | 6b 5b 52 20 26 20 33 31 |rightMas|k[R & 31|
|00002ff0| 5d 3b 0d 6c 6f 6e 67 20 | 6e 75 6d 4d 69 64 3d 28 |];.long |numMid=(|
|00003000| 52 3e 3e 35 29 2d 28 4c | 3e 3e 35 29 2d 31 3b 0d |R>>5)-(L|>>5)-1;.|
|00003010| 6c 6f 6e 67 20 78 2c 79 | 2c 70 61 64 3d 28 6d 61 |long x,y|,pad=(ma|
|00003020| 70 57 69 64 74 68 2d 6e | 75 6d 4d 69 64 2d 32 29 |pWidth-n|umMid-2)|
|00003030| 3c 3c 31 3b 0d 0d 20 20 | 69 66 20 28 6e 75 6d 4d |<<1;.. |if (numM|
|00003040| 69 64 3c 30 29 20 7b 4c | 4d 26 3d 52 4d 3b 52 4d |id<0) {L|M&=RM;RM|
|00003050| 3d 30 3b 7d 0d 0d 20 20 | 66 6f 72 20 28 79 3d 30 |=0;}.. |for (y=0|
|00003060| 3b 79 3c 48 3b 79 2b 2b | 29 20 7b 0d 20 20 20 20 |;y<H;y++|) {. |
|00003070| 2a 76 6d 20 5e 3d 20 4c | 4d 3b 20 76 6d 2b 2b 3b |*vm ^= L|M; vm++;|
|00003080| 0d 20 20 20 20 2a 76 6d | 20 7c 3d 20 4c 4d 3b 20 |. *vm| |= LM; |
|00003090| 76 6d 2b 2b 3b 0d 20 20 | 20 20 66 6f 72 20 28 78 |vm++;. | for (x|
|000030a0| 3d 30 3b 78 3c 6e 75 6d | 4d 69 64 3b 78 2b 2b 29 |=0;x<num|Mid;x++)|
|000030b0| 20 7b 0d 20 20 20 20 20 | 20 2a 76 6d 20 5e 3d 20 | {. | *vm ^= |
|000030c0| 30 78 46 46 46 46 46 46 | 46 46 3b 20 76 6d 2b 2b |0xFFFFFF|FF; vm++|
|000030d0| 3b 0d 20 20 20 20 20 20 | 2a 76 6d 20 7c 3d 20 30 |;. |*vm |= 0|
|000030e0| 78 46 46 46 46 46 46 46 | 46 3b 20 76 6d 2b 2b 3b |xFFFFFFF|F; vm++;|
|000030f0| 0d 20 20 20 20 7d 0d 20 | 20 20 20 69 66 20 28 52 |. }. | if (R|
|00003100| 4d 29 20 7b 0d 20 20 20 | 20 20 20 2a 76 6d 20 5e |M) {. | *vm ^|
|00003110| 3d 20 52 4d 3b 20 76 6d | 2b 2b 3b 0d 20 20 20 20 |= RM; vm|++;. |
|00003120| 20 20 2a 76 6d 20 7c 3d | 20 52 4d 3b 20 76 6d 2b | *vm |=| RM; vm+|
|00003130| 2b 3b 0d 20 20 20 20 7d | 0d 20 20 20 20 76 6d 2b |+;. }|. vm+|
|00003140| 3d 70 61 64 3b 0d 20 20 | 7d 0d 7d 0d 0d 2f 2a 20 |=pad;. |}.}../* |
|00003150| 50 61 63 6b 4d 61 70 20 | 72 65 64 75 63 65 73 20 |PackMap |reduces |
|00003160| 74 68 65 20 74 77 6f 20 | 69 6e 74 65 72 6c 65 61 |the two |interlea|
|00003170| 76 65 64 20 62 69 74 20 | 6d 61 70 73 20 75 73 65 |ved bit |maps use|
|00003180| 64 20 66 6f 72 0d 20 20 | 20 74 68 65 20 65 76 65 |d for. | the eve|
|00003190| 6e 20 70 61 72 69 74 79 | 20 63 61 73 65 2c 20 69 |n parity| case, i|
|000031a0| 6e 74 6f 20 61 20 73 69 | 6e 67 6c 65 20 62 69 74 |nto a si|ngle bit|
|000031b0| 20 6d 61 70 2e 20 20 45 | 61 63 68 0d 20 20 20 70 | map. E|ach. p|
|000031c0| 61 69 72 20 6f 66 20 77 | 6f 72 64 73 2c 20 6f 66 |air of w|ords, of|
|000031d0| 20 74 68 65 20 65 6e 74 | 69 72 65 20 62 69 74 6d | the ent|ire bitm|
|000031e0| 61 70 2c 20 69 73 20 58 | 4f 52 65 64 20 74 6f 67 |ap, is X|ORed tog|
|000031f0| 65 74 68 65 72 0d 20 20 | 20 72 65 67 61 72 64 6c |ether. | regardl|
|00003200| 65 73 73 20 6f 66 20 72 | 65 63 74 61 6e 67 6c 65 |ess of r|ectangle|
|00003210| 20 62 6f 75 6e 64 61 72 | 69 65 73 2e 0d 2a 2f 0d | boundar|ies..*/.|
|00003220| 76 6f 69 64 20 50 61 63 | 6b 4d 61 70 28 6c 6f 6e |void Pac|kMap(lon|
|00003230| 67 2a 20 76 6d 2c 6c 6f | 6e 67 20 6d 61 70 53 69 |g* vm,lo|ng mapSi|
|00003240| 7a 65 29 20 7b 0d 6c 6f | 6e 67 2a 20 76 6d 45 3d |ze) {.lo|ng* vmE=|
|00003250| 76 6d 3b 0d 6c 6f 6e 67 | 2a 20 65 6e 64 4f 66 4d |vm;.long|* endOfM|
|00003260| 61 70 3d 76 6d 2b 6d 61 | 70 53 69 7a 65 3b 0d 20 |ap=vm+ma|pSize;. |
|00003270| 20 77 68 69 6c 65 20 28 | 76 6d 3c 65 6e 64 4f 66 | while (|vm<endOf|
|00003280| 4d 61 70 29 20 7b 0d 20 | 20 20 20 2a 76 6d 2b 2b |Map) {. | *vm++|
|00003290| 20 3d 20 2a 76 6d 45 20 | 5e 20 76 6d 45 5b 31 5d | = *vmE |^ vmE[1]|
|000032a0| 3b 0d 20 20 20 20 76 6d | 45 2b 3d 32 3b 0d 20 20 |;. vm|E+=2;. |
|000032b0| 7d 0d 7d 0d 00 00 00 00 | 00 00 00 00 00 00 00 00 |}.}.....|........|
|000032c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000032d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000032e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000032f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003300| 00 00 01 00 00 00 05 68 | 00 00 04 68 00 00 00 46 |.......h|...h...F|
|00003310| 84 83 84 83 84 83 84 73 | 64 83 04 83 84 6b 64 83 |.......s|d....kd.|
|00003320| 04 83 84 83 84 83 84 83 | 84 83 84 83 84 83 84 83 |........|........|
|00003330| 10 49 6e 74 65 72 73 65 | 63 74 52 65 63 74 73 2e |.Interse|ctRects.|
|00003340| 63 74 02 00 00 00 54 45 | 58 54 52 2a 63 68 00 00 |ct....TE|XTR*ch..|
|00003350| 00 00 54 45 58 54 52 2a | 63 68 00 00 00 00 00 00 |..TEXTR*|ch......|
|00003360| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003370| 00 00 ad 38 16 f2 00 00 | 00 00 00 00 05 ae 01 83 |...8....|........|
|00003380| 04 83 84 83 84 83 84 f3 | 33 83 04 db 39 83 04 83 |........|3...9...|
|00003390| 84 83 84 83 84 83 84 83 | 84 83 84 83 84 0f 18 c8 |........|........|
|000033a0| 07 14 b9 66 10 fb 0a c1 | a0 d3 07 28 33 02 5c 14 |...f....|...(3.\.|
|000033b0| 40 0c f3 0a a2 20 03 0f | 5b 27 2b 06 63 01 14 2b |@.... ..|['+.c..+|
|000033c0| 06 16 07 03 d0 2b b8 2b | 06 0a 17 17 28 63 05 f3 |.....+.+|....(c..|
|000033d0| 52 7b 30 20 17 14 db 09 | 36 17 08 6f 9b 06 10 63 |R{0 ....|6..o...c|
|000033e0| 23 44 3b 30 04 5b 57 49 | 04 f3 52 9a 63 85 03 07 |#D;0.[WI|..R.c...|
|000033f0| 1b 0b 03 0b 93 0f 28 aa | 02 42 08 3b 1c 13 0f c1 |......(.|.B.;....|
|00003400| 00 00 00 48 00 09 4d 6f | 6e 61 63 6f 00 b3 74 a6 |...H..Mo|naco..t.|
|00003410| 04 b3 2f 72 04 b2 e4 1e | 04 b3 48 e8 00 00 00 00 |../r....|..H.....|
|00003420| 00 00 00 00 00 00 00 06 | 00 04 00 87 00 da 03 1e |........|........|
|00003430| 03 5a 00 87 00 da 03 1e | 03 5a ad 45 51 2c 00 00 |.Z......|.Z.EQ,..|
|00003440| 09 d0 00 00 09 d0 00 00 | 00 36 01 00 00 00 04 18 |........|.6......|
|00003450| 52 2a 63 68 00 80 00 08 | 00 00 00 48 00 48 00 00 |R*ch....|...H.H..|
|00003460| 00 00 02 db 02 40 ff e7 | ff ee 02 ff 02 52 1f 03 |.....@..|.....R..|
|00003470| 05 28 03 fc 00 01 00 00 | 01 2c 01 2c 00 00 00 00 |.(......|.,.,....|
|00003480| 0b e7 09 60 01 2c 00 2d | 05 a0 5e ec 00 26 02 01 |...`.,.-|..^..&..|
|00003490| 01 01 00 18 00 01 27 0f | 00 01 00 01 00 00 00 00 |......'.|........|
|000034a0| 00 00 00 00 00 00 00 00 | 00 01 00 00 00 00 00 00 |........|........|
|000034b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000034c0| 00 02 00 00 00 00 04 02 | 04 05 00 00 00 00 00 01 |........|........|
|000034d0| 06 4d 6f 6e 61 63 6f 98 | 00 00 00 00 00 00 00 00 |.Monaco.|........|
|000034e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000034f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003500| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003510| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003520| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003530| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003540| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003550| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003560| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003570| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003580| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003590| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000035a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000035b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000035c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000035d0| 00 09 00 00 00 04 09 48 | 65 6c 76 65 74 69 63 61 |.......H|elvetica|
|000035e0| 06 4d 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |.M......|........|
|000035f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003600| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003610| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003620| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003630| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003640| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003650| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003660| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003670| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003680| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003690| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000036a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000036b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000036c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000036d0| 00 00 00 00 00 00 0c 43 | 6f 6e 66 69 64 65 6e 74 |.......C|onfident|
|000036e0| 69 61 6c 08 09 48 00 00 | 00 00 00 00 00 00 00 00 |ial..H..|........|
|000036f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003700| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003710| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003720| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003730| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003740| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003750| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003760| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003770| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003780| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003790| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000037d0| 00 00 00 00 00 00 00 00 | 00 00 00 01 00 00 01 01 |........|........|
|000037e0| 00 00 80 00 00 00 80 00 | 00 00 80 00 00 00 80 00 |........|........|
|000037f0| 00 00 00 00 00 01 01 00 | 01 00 00 01 00 00 00 03 |........|........|
|00003800| 00 48 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |.H......|........|
|00003810| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003820| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003830| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003840| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003850| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00003860| 00 00 00 00 00 00 00 00 | 00 00 01 00 00 00 05 68 |........|.......h|
|00003870| 00 00 04 68 00 00 00 46 | 04 b3 4c bc 19 b6 00 00 |...h...F|..L.....|
|00003880| 00 1c 00 46 00 01 4d 50 | 53 52 00 00 00 12 42 42 |...F..MP|SR....BB|
|00003890| 53 54 00 00 00 1e 03 ed | ff ff 00 00 00 00 00 00 |ST......|........|
|000038a0| 00 00 00 80 ff ff 00 00 | 00 4c 04 b3 48 e8 00 00 |........|.L..H...|
|000038b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000038c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000038d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000038e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000038f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
+--------+-------------------------+-------------------------+--------+--------+
